纸上谈兵: 图 (graph)

快来打我* 2021-11-26 11:42 326阅读 0赞

作者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！

图(graph)是一种比较松散的数据结构。它有一些节点(vertice)，在某些节点之间，由边(edge)相连。节点的概念在树中也出现过，我们通常在节点中储存数据。边表示两个节点之间的存在关系。在树中，我们用边来表示子节点和父节点的归属关系。树是一种特殊的图，但限制性更强一些。

这样的一种数据结构是很常见的。比如计算机网络，就是由许多节点(计算机或者路由器)以及节点之间的边(网线)构成的。城市的道路系统，也是由节点(路口)和边(道路)构成的图。地铁系统也可以理解为图，地铁站可以认为是节点。基于图有许多经典的算法，比如求图中两个节点的最短路径，求最小伸展树等。

图的经典研究是柯尼斯堡七桥问题(Seven Bridges of Königsberg)。柯尼斯堡是现今的加里宁格勒，城市中有一条河流过，河中有两个小岛。有七座桥桥连接河的两岸和两个小岛。送信员总想知道，有没有一个办法，能不重复的走过7个桥呢？

(这个问题在许多奥数教材中称为"一笔画"问题)

![SouthEast][]

欧拉时代的柯尼斯堡地图

柯尼斯堡的可以看作由7个边和4个节点构成的一个图:

![SouthEast 1][]

这个问题最终被欧拉巧妙的解决。七桥问题也启发了一门新的数学学科——图论(graph theory)的诞生。欧拉的基本思路是，如果某个节点不是起点或者终点，那么连接它的边的数目必须为偶数个(从一个桥进入，再从另一个桥离开)。对于柯尼斯堡的七桥，由于4个节点都为奇数个桥，而最多只能有两个节点为起点和终点，所以不可能一次走完。

### 图的定义 ###

严格的说，图\[$G = (V, E)$\]是由节点的集合V和边的集合E构成的。一个图的所有节点构成一个集合\[$V$\]。一个边可以表示为\[$(v\_1, v\_2)$\]，其中\[$v\_1, v\_2 \\in V$\]，即两个节点。如果\[$(v\_1, v\_2)$\]有序，即\[$(v\_1, v\_2)$\]与\[$(v\_2, v\_1)$\]不同，那么图是有向的(directed)。有序的边可以理解为单行道，只能沿一个方向行进。如果\[$(v\_1, v\_2)$\]无序，那么图是无向的(undirected)。无序的边可以理解成双向都可以行进的道路。一个无序的边可以看作连接相同节点的两个反向的有序边，所以无向图可以理解为有向图的一种特殊情况。

(七桥问题中的图是无向的。城市中的公交线路可以是无向的，比如存在单向环线)

图的一个路径(path)是图的一系列节点\[$w\_1, w\_2, ..., w\_n$\]，且对于\[$1 \\le i < n $\]，有\[$ (w\_i, w\_\{i+1\}) \\in E$\]。也就是说，路径是一系列的边连接而成，路径的两端为两个节点。路径上边的总数称为路径的长度。乘坐地铁时，我们会在选择某个路径，来从A站到达B站。这样的路径可能有不止一条，我们往往会根据路径的长度以及沿线的拥挤状况，来选择一条最佳的路线。如果存在一条长度大于0的路径，该路径的两端为同一节点，那么认为该图中存在环路(cycle)。很明显，上海的地铁系统中存在环路。

![SouthEast 2][]

找到一条环路

如果从每个节点，到任意一个其它的节点，都有一条路径的话，那么图是连通的(connected)。对于一个有向图来说，这样的连通称为强连通(strongly connected)。如果一个有向图不满足强连通的条件，但将它的所有边都改为双向的，此时的无向图是连通的，那么认为该有向图是弱连通(weakly connected)。

如果将有火车站的城市认为是节点，铁路是连接城市的边，这样的图可能是不连通的。比如北京和费城，北京有铁路通往上海，费城有铁路通往纽约，但北京和费城之间没有路径相连。

### 图的实现 ###

一种简单的实现图的方法是使用二维数组。让数组a的每一行为一个节点，该行的不同元素表示该节点与其他节点的连接关系。如果\[$(u, v) \\in E$\]，那么a\[u\]\[v\]记为1，否则为0。比如下面的一个包含三个节点的图:

![SouthEast 3][]

可以简单表示为

这种实现方式所占据的空间为\[$O(|V|^2)$\]，\[$|V|$\]为节点总数。所需内存随着节点增加而迅速增多。如果边不是很密集，那么很多数组元素记为0，只有稀疏的一些数组元素记为1，所以并不是很经济。

更经济的实现方式是使用邻接表(adjacency list)，即记录每个节点所有的相邻节点。对于节点m，我们建立一个链表。对于任意节点k，如果有\[$(m, k) \\in E$\]，就将该节点放入到对应节点m的链表中。邻接表是实现图的标准方式。比如下面的图，

![SouthEast 4][]

可以用如下的数据结构实现：

![SouthEast 5][]

左侧为一个数组，每个数组元素代表一个节点，且指向一个链表。该链表包含有该数组元素所有的相邻元素。邻接表所占据的空间为\[$O(|V| + |E|)$\](数组占据\[$|V|$\])的空间，即节点的总数。链表占据\[$|E|$\]的空间，即边的总数。

上面的实现主要基于链表，所以具体的代码可参考[纸上谈兵: 表 (list)][_ _list] 。

### 总结 ###

图是一种很简单的数据结构。图的组织方式比较松散，自由度比较大，但也造成比较高的算法复杂度。我将在以后介绍一些图的经典算法。

欢迎继续阅读[“纸上谈兵: 算法与数据结构”][Link 1]系列。

[SouthEast]: /images/20211126/3f5d89859bbe40ea82bf60ceb4c81297.png
[SouthEast 1]: /images/20211126/5b075cb48dfa4b4f81a6f61c3c802e1f.png
[SouthEast 2]: /images/20211126/27c564fdd7454af5993b4446edc94eb9.png
[SouthEast 3]: /images/20211126/cc83a4e2dfff4ac18677f5b7258f7820.png
[SouthEast 4]: /images/20211126/a931b1be5c984ca08f417fb20a6dff3d.png
[SouthEast 5]: /images/20211126/2075b998b2cd4d80ba30764f0b9d83e2.png
[_ _list]: http://www.cnblogs.com/vamei/archive/2013/03/14/2958940.html
[Link 1]: http://www.cnblogs.com/vamei/archive/2013/03/22/2974052.html