图的邻接表和邻接矩阵

水深无声 2023-10-12 08:31 19阅读 0赞

### 图的邻接表和邻接矩阵 ###

*  图的定义
 *  邻接矩阵
 *   *  样例代码
 *  邻接表
 *   *  样例代码
 *  使用场景

# 图的定义 #

图是由顶点集合和顶点之间边的集合组成。通常表示为G(V, E), 其中G表示图，V是G中顶点的集合，E是G中边的集合。

比如说，在图G1中，有0到4这5个顶点，0-1、0-2、0-4、1-2、2-3、3-4这六条边。那么根据图中边的方向，我们可以分为无向图和有向图，那么根据边长是否有权重，可以分为带权图和不带权图。

![在这里插入图片描述][c15017e14b4e4259b5d7f7cdb60e0820.png]  
例如，G1是无向图，0和1之间有一条边，0到1和1到0是等价的。

G2是有向图，1到0有一条边，所以从1可以到0，但是从0不能到1。

G3是带权的无向图，顶点之间的边加上了权重的度量。这种度量可能表示的是距离、代价、时间等等具体的量。  
![在这里插入图片描述][1b787298b86e4680807782489c547da2.png]  
如果0、1、2、3、4代表5个城市，那么0到1、0到2这些边就可以代表城市间的距离。

G4是带权有向图，特别要注意，两顶点之间不同方向边的权重可以是不同的。例如，3到4的边长是70, 4到3的边长是60。

# 邻接矩阵 #

我们可以使用二维数组来表示图，该数组我们也称为邻接矩阵。例如，使用邻接矩阵表示G1、2、3、4。  
![在这里插入图片描述][15988758875e4ab1858290ff1fb56165.png]  
![在这里插入图片描述][10dfbc78549d4d708040ae9c12fa4358.png]  
不带权的邻接矩阵中1代表两顶点联通，0代表不连通。某顶点到它本身的边一般标记为0。根据需要也可以标记为1，带权图的邻接矩阵中，不连通顶点之间的边权值是正无穷来表示两顶点之间无法到达。而对角线是0，表示某定点到自己的边长为0。

另外无向图的邻接矩阵是以0-0、1-1、2-2这条对角线对称的。  
![在这里插入图片描述][aa4c4e75eeac4cbe853a12dc29315c77.png]

## 样例代码 ##

首先声明一个5乘5的二维数组Graph，其中全部元素初始化为0。

然后将Graph 0-2、0-4、1-0等等设置为1，将相应的顶点进行连接。

最后打印二维数组。这样就完成了G2有向图的表示。

另外在带权图的邻接矩阵中，正无穷会取一个具体的、非常大的数字。需要大于其他有效的边长。比如在图G3表示的问题中，边长不会超过1000，那么如果0无法到达3，`G[0][3]`可以取值4个9，来表示两顶点无法到达。  
![在这里插入图片描述][b79067c69645441e8147715828bdc279.png]

# 邻接表 #

除了使用数组存储图，还可以使用链表，这种表示方法被称为图的邻接表。它是一种顺序和链式相结合的存储结构。表头是一个图的节点数组，对应图的顶点，每个节点后连接一个链表或者指针数组。存储与这个顶点相连的其他顶点的指针。

那么无论是有向图还是无向图，带权或者是不带权，只要顶点A到顶点B之间有一条边，则A对应的表头后就有一个顶点B的指针，例如 0到2和3有一条边，那么表头0后有2和3对应的节点指针有一条边，这里指针的连接代表了相连，如果需要增加权值，可以在表示边的节点结构中增加额外的数据域存储。

## 样例代码 ##

具体的，定义图的节点结构体GraphNode，其中label表示图的顶点编号，neighbors存储与该顶点相邻的节点指针，表示该节点到这些节点有一条边。

![在这里插入图片描述][62584c78b6bb406995471c1b0953b301.png]  
创建长度为4的图顶点结构体数组。0、1、2、3四个顶点就对应了G\[0\]、G\[1\]、G\[2\]、G\[3\]四个结构体。它们就是邻接表的表头。然后使用循环为表头中的label赋值。G\[i\]的label等于i，顶点编号赋值为0、1、2、3。为了表示图中边的指向关系，G\[0\]的neighbors中存储指向G\[2\]和G\[3\]的指针。G\[1\]的neighbors中存储指向G\[0\]和G\[2\]的指针。通过push\_back添加0到2和3的边。添加1到0和2的边。添加2到3的边，3到0的边。这样就构造出了图G对应的邻接表。最后使用循环打印邻接表。

我们一般根据顶点和边的数量关系来选择邻接矩阵或者邻接表来存储图。根据边与顶点的关系，图可以定义为稀疏图和稠密图。如果边的条数E远小于顶点数量V的平方，这种图被称为稀疏图。反之边的条数E接近V的平方时，该图被称为稠密图。例如在有向图G2中，有5个顶点，7条边，根据7小于25，并且不接近25，可以认为G2是一个稀疏图。  
![在这里插入图片描述][948e78c6e88c47de9e2b853afd142456.png]

# 使用场景 #

我们一般使用邻接表表示稀疏图，邻接矩阵表示稠密图，因为邻接表会随着边数量的增加而增加表示边的节点。而无论图中有多少条边，邻接矩阵都对应一个V平方的二维数组。所以说根据这种关系选择数据结构，我们就可以较大的提高图存储的效率。  
![在这里插入图片描述][fff0a5b637934d32844e99f0bd5eeab8.png]  
不过在一些特殊的条件下，我们需要使用特定的表示方法，例如希望快速判断任意两个节点之间是否有边相连。因为二位数组的访问时间复杂度是O(1), 所以说这种情况就需要使用邻接矩阵表示图。

**参考资料**：[看动画，彻底理解数据结构中图的知识，图的邻接表和邻接矩阵][Link 1]

[c15017e14b4e4259b5d7f7cdb60e0820.png]: https://img-blog.csdnimg.cn/c15017e14b4e4259b5d7f7cdb60e0820.png
[1b787298b86e4680807782489c547da2.png]: https://img-blog.csdnimg.cn/1b787298b86e4680807782489c547da2.png
[15988758875e4ab1858290ff1fb56165.png]: https://img-blog.csdnimg.cn/15988758875e4ab1858290ff1fb56165.png
[10dfbc78549d4d708040ae9c12fa4358.png]: https://img-blog.csdnimg.cn/10dfbc78549d4d708040ae9c12fa4358.png
[aa4c4e75eeac4cbe853a12dc29315c77.png]: https://img-blog.csdnimg.cn/aa4c4e75eeac4cbe853a12dc29315c77.png
[b79067c69645441e8147715828bdc279.png]: https://img-blog.csdnimg.cn/b79067c69645441e8147715828bdc279.png
[62584c78b6bb406995471c1b0953b301.png]: https://img-blog.csdnimg.cn/62584c78b6bb406995471c1b0953b301.png
[948e78c6e88c47de9e2b853afd142456.png]: https://img-blog.csdnimg.cn/948e78c6e88c47de9e2b853afd142456.png
[fff0a5b637934d32844e99f0bd5eeab8.png]: https://img-blog.csdnimg.cn/fff0a5b637934d32844e99f0bd5eeab8.png
[Link 1]: https://www.bilibili.com/video/BV1D5411c71o/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb