9.1 图¶
图(graph)是一种非线性数据结构,由顶点(vertex)和边(edge)组成。我们可以将图 \(G\) 抽象地表示为一组顶点 \(V\) 和一组边 \(E\) 的集合。以下示例展示了一个包含 5 个顶点和 7 条边的图。
如果将顶点看作节点,将边看作连接各个节点的引用(指针),我们就可以将图看作一种从链表拓展而来的数据结构。如图 9-1 所示,相较于线性关系(链表)和分治关系(树),网络关系(图)的自由度更高,因而更为复杂。
图 9-1 链表、树、图之间的关系
图解 9-1:链表、树与图的连接关系
用同样的五个节点比较线性后继、树形层级与允许跨分支连接和环路的网络关系。
从左到右三幅子图均使用编号 1 至 5 的五个节点:单向链表与树的箭头表示有向引用,无向图的线段表示双向邻接。它们是并列的结构对比,不是将同一结构逐步变形的算法。
按连接约束从严到宽对比:单向链表要求每个非尾节点仅有一个后继,呈单一线性链;树允许一个父节点分出多个子节点,形成自根向下的层级分支,但每个非根节点只有一个父节点且不能跨分支或成环;图则解除根与层级限制,任意两个顶点之间均可按关系建立连接,并允许出现环路。
右侧“无向图”子图下方的“逻辑自由度最高”指连接约束最少,不是某次算法的复杂度。下表列出三种结构的完整连接。
| 结构 | 完整连接 | 连接约束与本例特征 |
|---|---|---|
| 单向链表 | 1→2、2→3、3→4、4→5 | 4 条后继引用;一条线;尾节点 5 无后继 |
| 树 | 1→2、1→3、2→4、2→5 | 4 条父子引用;根为 1;叶为 3、4、5 |
| 无向图 | 1—2、1—3、1—5、2—3、2—4、2—5、4—5 | 7条无向边;有环,并非完全图 |
本例无向图有 1—2—3—1、2—4—5—2 等环路,但 3 与 4、3 与 5 未相连,并非完全图。把节点视为顶点、引用视为边,可以从图的角度理解链表与树。
9.1.1 图的常见类型与术语¶
根据边是否具有方向,可分为无向图(undirected graph)和有向图(directed graph),如图 9-2 所示。
- 在无向图中,边表示两顶点之间的“双向”连接关系,例如微信或 QQ 中的“好友关系”。
- 在有向图中,边具有方向性,即 \(A \rightarrow B\) 和 \(A \leftarrow B\) 两个方向的边是相互独立的,例如微博或抖音上的“关注”与“被关注”关系。
图 9-2 有向图与无向图
图解 9-2:无向图与有向图:无向双向边与独立有向边的对比
同样的顶点布局,用无向线段与有向箭头对比边的方向约束。
左右两幅图均包含编号 1、2、3、4、5 的五个顶点,且几何排布完全相同(左上 1、左下 3、中上 5、中下 2、右侧 4),专门对比边是否具有方向。
左侧为“无向图(边无方向)”:共有 7 条不带箭头的无向边 1—2、1—3、1—5、2—3、2—4、2—5、4—5。每条无向边天然代表两个顶点之间的双向连接关系,例如边 1—5 同时允许从 1 到 5 和从 5 到 1。
右侧为“有向图(边有方向)”:共有 9 条箭头,按起点列出为 1→3、2→1、2→4、2→5、3→1、3→2、4→5、5→1、5→4。顶点 1 与 3、4 与 5 之间各有两条方向相反的箭头,其余五处连接只有单向箭头。
两个方向的有向边彼此独立。例如右图有 5→1,没有直接的 1→5;从 1 仍可经 1→3→2→5 间接到达 5。双向直接互达需要两条相反的有向边,不能把间接路径当成直接边。
根据所有顶点是否连通,可分为连通图(connected graph)和非连通图(disconnected graph),如图 9-3 所示。
- 对于连通图,从某个顶点出发,可以到达其余任意顶点。
- 对于非连通图,从某个顶点出发,至少有一个顶点无法到达。
图 9-3 连通图与非连通图
图解 9-3:连通图与非连通图:所有顶点皆可达与存在孤立顶点
比较五个顶点全部可达与存在孤立顶点的两种连接情况。
左右两幅图均为包含顶点 1、2、3、4、5 的无向图。无向图的“连通”是指从任意顶点出发,都能沿一条或多条边组成的路径到达其余任意顶点,不要求每对顶点之间都有直接相连的边。
左侧为“连通图(所有顶点皆可达)”:共有七条无向边 1—2、1—3、1—5、2—3、2—4、2—5、4—5。即使像顶点 3 与顶点 4 之间没有直接边,也能通过路径 3—2—4 或 3—1—5—4 互相到达,因此五个顶点构成单一连通整体。
右侧为“非连通图(存在顶点不可达)”:保留了左侧四个顶点之间的五条无向边 1—2、1—3、1—5、2—3、2—5,但删去了连接顶点 4 的两条边 2—4 和 4—5。此时顶点 1、2、3、5 内部依然彼此可达,但没有任何路径能够通往右图中孤立的顶点 4。
右图分为连通子集 {1, 2, 3, 5} 与孤立顶点 {4}。只要存在至少一对顶点无法沿路径互达,整个无向图就是非连通图。
我们还可以为边添加“权重”变量,从而得到如图 9-4 所示的有权图(weighted graph)。例如在《王者荣耀》等手游中,系统会根据共同游戏时间来计算玩家之间的“亲密度”,这种亲密度网络就可以用有权图来表示。
图 9-4 有权图与无权图
图解 9-4:无权图与有权图:为边附加权重数值属性
在相同连接上附加数值权重,对比无权图与有权图。
左右两幅图都有顶点 1 至 5 和相同的七条无向边,完整边集见下表。左侧“无权图(所有边等价)”不标数值;右侧“有权图(边具有权重属性)”在边旁标出小数。
“所有边等价”指已存在的边不区分强弱或长短,不表示所有顶点两两相连。右图权重范围为 0.2 至 1.0;图上没有指定物理单位。下表把每条边的数值和画面位置合在一行,均来自原图。
| 边 | 权重 | 画面位置 |
|---|---|---|
| 1—2 | 0.5 | 中间斜边 |
| 1—3 | 0.2 | 左侧竖边 |
| 1—5 | 0.25 | 上方边 |
| 2—3 | 0.3 | 下方横边 |
| 2—4 | 1.0 | 右下斜边 |
| 2—5 | 0.7 | 中间竖边 |
| 4—5 | 0.88 | 右上斜边 |
加上权重没有改变顶点与边的连接。结合应用,权重可表示距离、耗费或亲密度等量,为最短路径、最小生成树等计算提供依据。
图数据结构包含以下常用术语。
- 邻接(adjacency):当两顶点之间存在边相连时,称这两顶点“邻接”。在图 9-4 中,顶点 1 的邻接顶点为顶点 2、3、5。
- 路径(path):从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。在图 9-4 中,边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径。
- 度(degree):一个顶点拥有的边数。对于有向图,入度(in-degree)表示有多少条边指向该顶点,出度(out-degree)表示有多少条边从该顶点指出。
9.1.2 图的表示¶
图的常用表示方式包括“邻接矩阵”和“邻接表”。以下使用无向图进行举例。
1. 邻接矩阵¶
设图的顶点数量为 \(n\) ,邻接矩阵(adjacency matrix)使用一个 \(n \times n\) 大小的矩阵来表示图,每一行(列)代表一个顶点,矩阵元素代表边,用 \(1\) 或 \(0\) 表示两个顶点之间是否存在边。
如图 9-5 所示,设邻接矩阵为 \(M\)、顶点列表为 \(V\) ,那么矩阵元素 \(M[i, j] = 1\) 表示顶点 \(V[i]\) 到顶点 \(V[j]\) 之间存在边,反之 \(M[i, j] = 0\) 表示两顶点之间无边。
图 9-5 图的邻接矩阵表示
图解 9-5:无向图的邻接矩阵
以顶点列表确定行列索引,用矩阵交叉单元表示两点之间是否有边。
左侧是五顶点、七条边的无向图,右侧用 5×5 邻接矩阵表示。顶点列表 V=[1, 3, 2, 5, 4] 按此顺序对应行、列索引 0 至 4;顶点编号与索引不能混用。表头同时标出索引和顶点,查询时先确定对应索引。
邻接矩阵元素 M[i, j]=1 表示索引 i 的顶点 V[i] 与索引 j 的顶点 V[j] 之间有边相连,M[i, j]=0 表示无边。由于无向图的每条边在两个方向上等价,同一条无向连接会同时在 M[i, j] 和 M[j, i] 两处记为 1,使矩阵关于主对角线对称;本图无自环,主对角线 M[i, i] 全为 0。因此七条无向边共对应 14 个值为 1 的单元。
图中用颜色高亮标出三组无向边与矩阵对称单元的对应:边 1—2(索引 0 与 2)对应 M[0, 2]=1 与 M[2, 0]=1;边 3—2(索引 1 与 2)对应 M[1, 2]=1 与 M[2, 1]=1;边 5—4(索引 3 与 4)对应 M[3, 4]=1 与 M[4, 3]=1。下表列出完整矩阵。
| 行:索引/顶点 | 列 0/顶点 1 | 列 1/顶点 3 | 列 2/顶点 2 | 列 3/顶点 5 | 列 4/顶点 4 |
|---|---|---|---|---|---|
| 0/1 | 0 | 1 | 1 | 1 | 0 |
| 1/3 | 1 | 0 | 1 | 0 | 0 |
| 2/2 | 1 | 1 | 0 | 1 | 1 |
| 3/5 | 1 | 0 | 1 | 0 | 1 |
| 4/4 | 0 | 0 | 1 | 1 | 0 |
查顶点 3 与顶点 4 时,先找到索引 1 与 4,再读 M[1, 4]=0,得知两点无边。不要把顶点编号直接当成矩阵索引。
邻接矩阵具有以下特性。
- 在简单图中,顶点不能与自身相连,此时邻接矩阵主对角线元素没有意义。
- 对于无向图,两个方向的边等价,此时邻接矩阵关于主对角线对称。
- 将邻接矩阵的元素从 \(1\) 和 \(0\) 替换为权重,则可表示有权图。
使用邻接矩阵表示图时,我们可以直接访问矩阵元素以获取边,因此增删查改操作的效率很高,时间复杂度均为 \(O(1)\) 。然而,矩阵的空间复杂度为 \(O(n^2)\) ,内存占用较多。
2. 邻接表¶
邻接表(adjacency list)使用 \(n\) 个链表来表示图,链表节点表示顶点。第 \(i\) 个链表对应顶点 \(i\) ,其中存储了该顶点的所有邻接顶点(与该顶点相连的顶点)。图 9-6 展示了一个使用邻接表存储的图的示例。
图 9-6 图的邻接表表示
图解 9-6:图的邻接表表示
把每个顶点的邻居串成一行链表,表示原图的连接。
左侧无向图包含五个顶点 1、2、3、4、5,以及七条无向边 1—3、1—5、3—2、2—5、2—4、5—4、1—2。
右侧“邻接表”左列标为“顶点”,自上而下按 1、3、2、5、4 排列五个绿色头节点;每行向右延伸绿色链表,标为“与该顶点相连的所有顶点”。下表保留各行的画面顺序。
行内向右的箭头只表示链表节点引用,不表示原图中的有向边;同一行相邻的两个邻居也不一定在原图中直接相连。每条无向边在两个端点的邻接列表中各登记一次,共 14 个邻接节点,不含左列五个头节点。
| 顶点 | 邻居,按图中顺序 |
|---|---|
| 1 | 2、3、5 |
| 3 | 1、2 |
| 2 | 1、3、5、4 |
| 5 | 1、2、4 |
| 4 | 2、5 |
例如无向边 1—2 对应顶点 1 链表中的 2 和顶点 2 链表中的 1;顶点 1 与 4 没有边,所以彼此不出现在对方的链表中。
邻接表仅存储实际存在的边,而边的总数通常远小于 \(n^2\) ,因此它更加节省空间。然而,在邻接表中需要通过遍历链表来查找边,因此其时间效率不如邻接矩阵。
观察图 9-6 ,邻接表结构与哈希表中的“链式地址”非常相似,因此我们也可以采用类似的方法来优化效率。比如当链表较长时,可以将链表转化为 AVL 树或红黑树,从而将时间效率从 \(O(n)\) 优化至 \(O(\log n)\) ;还可以把链表转换为哈希表,从而将时间复杂度降至 \(O(1)\) 。
9.1.3 图的常见应用¶
如表 9-1 所示,许多现实系统可以用图来建模,相应的问题也可以约化为图计算问题。
表 9-1 现实生活中常见的图
| 顶点 | 边 | 图计算问题 | |
|---|---|---|---|
| 社交网络 | 用户 | 好友关系 | 潜在好友推荐 |
| 地铁线路 | 站点 | 站点间的连通性 | 最短路线推荐 |
| 太阳系 | 星体 | 星体间的万有引力作用 | 行星轨道计算 |