数据结构与算法-图论邻接矩阵【十四】

ゝ一世哀愁。 2023-03-02 05:25 16阅读 0赞

### 图的定义 ###

数据之间的关系可能是多种的，**逻辑结构**上来讲，分几种：

*  线性结构
 *  非线性结构 【包括三种: 集合结构，树形结构，图状结构】

> 线性结构

**线性结构**的几种表现方式，前面大部分都了解过了：

*  线性表 （List）
 *  栈（特殊的线性表） 【先进后出】 （Stack）
 *  队列（特殊的线性表）【先进先出】 （Queue）
 *  字符串，数组，广义表【广义表是特殊的线性表，广义表的元素可以是子表，子表的元素也可以是子表；如果广义表的每个元素都是原子，它就变成了线性表】

> 非线性结构

非线性结构中的[ 树(click me) ][_click me_]，各个数据之间的关系是一对多。

那么图 与树的区别就是，各个数据之间的关系是多对多。 图又有无向图与有向图，无向图为各个数据之间的关系是没有方向的，有向图反之，数据间是有方向的概念的。

--------------------

#### 顺序存储（数组表示） ####

如果一定用数组的话，需要一个二维数组来表示数据与数据之间的关系。 【邻接矩阵】

数组（邻接矩阵）表示法

1，需要一个（顶点）表，记录各个顶点的信息

2，一个**邻接矩阵** 存储各个顶点之间的关系

假如图A = G(V, E),有 `n`个顶点

*  顶点表为一个一纬数组 `Vexs[n]`，表示每个顶点代表的数据
 *  邻接矩阵是一个二维数组 `Arcs[n][n]` ,表示各个顶点之间的关系

图中各个顶点的关系存在方向的情况下，节点只能单向通信，图就变成了有向图，。

##### 无向图的邻接矩阵 #####

1，无向图的邻接矩阵是对称矩阵  
2，顶点的度就是第i行（列）中`1`的个数。  
完全图的邻接矩阵，对角线为0，其余全部是1。

##### 有向图的邻接矩阵 #####

注意：有向图的第`i`行中1的个数表示以`Vi`为起点的弧（出度边）；有向图的第`i`列中1的个数表示以`Vi`为终点的弧（入度边）

1，有向图的邻接矩阵可能不是对称矩阵  
2，顶点的出度 就是第`i`行非0元素的个数总和  
3，顶点的入度 就是第`i`列非0元素的个数总和

四字真言：**行出列入**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70]

##### 有向网的邻接矩阵 #####

什么是有向网，就是有向图中，具有方向的两个顶点之间存在一个特殊意义的数据，比如权重值。将上面有向图的1改为存在特殊意义的权重值即可。

如果用javascript代码来表示应该是这样：

vexs 是一位数组，存放n个顶点,arcs 是一个二维数组，存放各个顶点之间的关系和数据
    顶点为n个，那么arcs是n*n的二维数组

function Graph(vexs = [], arcs = []) { 
          this.vexs = vexs
          this.arcs = arcs
        }

##### 邻接矩阵的优缺点 #####

优点：

1.  查找某一个顶点的出度与入度很方便
2.  查找某两个顶点的权值也很方便

缺点：

1.  不利于添加和删除点
2.  空间复杂度为`n^2` ，在存储稀疏图（顶点很多，但是边很少）的时候，会浪费大量存储空间
3.  在统计图中有多少条边的情况下，需要遍历整个arcs数组，时间复杂度为`n^2`, 浪费时间

--------------------

#### 链式存储 （链式表示） ####

链式表表示法----【邻接表/ 邻接多重表 / 十字链表】

TO BE CONTINUED

[_click me_]: https://blog.csdn.net/a5534789/article/details/105613915
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70]: /images/20230208/2dfb391006b747f993605248ec47080c.png

数据结构与算法-图论邻接矩阵【十四】

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关数据结构——邻接矩阵实现图

相关数据结构与算法-图论邻接表【十五】

相关数据结构与算法-图论邻接矩阵【十四】

相关数据结构-有向图邻接表邻接矩阵

相关【数据结构】图的存储--邻接矩阵

相关数据结构图的邻接矩阵

相关 java数据结构-----图（邻接矩阵和邻接表）

相关数据结构之图论之邻接矩阵（数组表示法）

相关数据结构——图的存储（邻接矩阵）

相关【数据结构】图的存储结构：邻接矩阵