127
6
图算法
图是一种用于表示复杂结构化信息的基本结构。图
6-1
中的所有图片都是图的示例。
本章将会讨论图的通用表示法以及相关的一些使用较为频繁的图算法。从本质上来说,
一个图会包含一个元素集合(也称为
顶点
)以及这些元素两两之间的关系(也称为
)。
本章会一直沿用这些术语,虽然在其他描述中也可能会使用术语“结点”和“连接”来
表示相同的概念。此外,这里仅讨论简单图以避免两类情况:顶点有指向自己的边;相
同顶点对之间存在多条边。
图中边所定义的结构使得许多问题都可以描述为:借助图中已有的边,查找从源顶点到
目标顶点的路径。有的时候边会有数值(也称为权值)相关联,还有些时候边带有特定
方向(例如单行道
源点最短路径
是这样的一种算法:给定一个顶点
s
,要求计算
出该顶点到图中其他所有顶点的最短路径(边的权值
和)。而
所有点对最短路径
问题
要计算图中所有顶点对
(
u
,
v
)
之间的最短路径。
某些问题则需要更为深入地理解图的结构。例如,无向带权图的最小生成树(
MST
)是
图中边的子集,它满足的条件有:原有的顶点集合在
MST
中依旧相互通;
MST
中边
权值之和最小。本章将展示如何使用
Prim
算法
来高效地解决这个问题。
6.1
G = (
V
,
E
)
由顶点集合
V
以及连接这些顶点对的边集
E
定义
。常见的类图如下:
无向无权图
这种图构建了顶点
(
u
,
v
)
之间不考虑方向的关系。在
采集对称信息时,这种图非常有
用。例如,在社交网络图中,如果
Alice
Bob
的朋友,那么
Bob
也是
Alice
的朋友。
128
6
᪞૰ᅃ๘
ࢲҾబ
ᅉ෩Ԟઙ
ֱ૙࿵๘
᫇ڱళᅃ๘
Ҿబ
ᅉ෩Ԟઙ
ஒ૧ჱ
கਖ਼ဇ௝
૧Ҿܾ๘
฽Ҿు
Ҹն༬࿵๘
᪞૰ܾ๘
Ҿబ
ֱ૙ܾ๘
ྰ૸
࿵๘
ુబ༬
᪞૰ෙ๘
ஒ߭ૢ༬ ᫇ڱళܾ๘ ஒૢჱĄҾబ
᫇ڱళෙ๘
ஒૢჱĄҾబ
᪞૰຺๘
ஒૢჱĄҾబ
ֱ૙ܾ๘
ஒૢჱĄҾబ!
6-1a)西班牙查理二世(16611700)族谱;b)有关肝癌的分子网络
有向图
这种图构建的顶点
(
u
,
v
)
之间的关系和顶点
v
,
u
之间的关系不同,后者或许不存在。
例如,提供驾驶信息的程序必须存储单行道的信息,以免给出错误的方向。
图算法
129
图算法
带权图
这种图构建的顶点
(
u
,
v
)
之间的关系附有数值
也称为
权值
。有时,这些值可以存
储任意非数值的信息。例如
A
镇和
B
镇之间的边可以存储相距的公里数,也可以
存储旅行需要的分钟数或者街道、公路的名称。
最为高度结构化的图是有向带权图,它定义了一个非空顶点集合
{
v
0
,
v
1
,
,
v
n
1
}
连接
这些不同顶点对的有向边(这样可以使每对顶点在每个方向上最多只有一条边),以及
与每条边相关联的正数权值。在许多应用中,权值表示距离或者费用。而对某些应
用来说,它们或许希望能够放宽权必须为正的限制(例如,负值可以用于反映损失而
非盈利),若出现这种情况,我们会进行一定的声明。
考虑图
6-2
的有向带权图,它由
6
个顶点和
5
条边组成。它可以使用如图
6-3
所示的邻
接表的方式进行存储,其中每个顶点
v
i
维护了一个结点链表,链表中的每个结点存放了
v
i
到相邻顶点的边的权值因此,这种基本的结构就是由图中顶点组成的一维数组。
6-2:有向带权图示例
6-3:有向带权图的邻接表表示
6-4
展示了如何用一个
n
阶的邻接矩阵
A
来存储有向带权图,邻接矩阵支持使用顶点
从两个维度进行索引。
A
[
i
][
j
]
存储了从
v
i
v
j
的边的权值;当
v
i
v
j
不存在边时,
A
[
i
][
j
]
会被设置为一些特殊值,如
0
1
甚至负无穷大。我们也可以使用邻接表和邻接矩阵
来存储无向图(可以用值
1
来代表一条边)。使用邻接矩阵,检查一条边
(
v
i
v
j
)
否存在只需要常数时间而使用邻接表所需时间依赖于
v
i
链表中的边的数量。相反,使
130
6
用邻接矩阵需要更多的空间,并且需要更多的时间才能找出某个顶点所有的边,因为它
需要检查所有可能的边,而这样的费用在顶点数目变得较多时非常大。对于
稠密图
(几
乎所有边都可能连接每一个顶点)而言,应当使用邻接矩阵进行表示。
6-4:有向带权图的邻接矩阵表示
我们使用
<
v
0
v
1
,…
v
k-1
>
来描述图中遍历
k
个顶点的一条路径,这条路径遍历了
k
1
条边
(
v
i
,
v
i+1
)
,其中
0
i
<
k
1
,有向图中的路径需要遵循边的方向。在图
6-2
中,路径
<
v
4
v
5
v
2
v
4
v
1
>
是有效的。该图存在一个
,即某条路径中多次包含相同的顶点。
环通常使用它的最小形式表示。如果图中任意两个顶点之间存在路径,那么该图是
连通
的。
当使用邻接表来存储无向图时,同一条边
(
u
,
v
)
在邻接表中出现了两次:一次是在
u
邻接顶点链表中,另一次是在
v
的邻接顶点链表中。因此,相比同样数目的顶点和边的
有向图,无向图在邻接表中的存储可能需要两倍的存储空间。在这种情况下,定位顶点
u
的邻居节点所需的时间与该顶点实际的邻居节点数且成正比。而在使用邻接矩阵存储
无向图时,
A
[
i
][
j
] =
A
[
j
][
i
]
数据结构设计
我们使用
C++
版本的
Graph
类来存储有向(或无向)图。
Graph
类借助
C++
标准模板库
STL
)的核心类实现了邻接表的表示。具体点说,它将图信息存储成一个由链表
list
对象组成的数组,其中每个链表对应于一个顶点。对于每一个顶点
u
,它都会一个由
整数类型的
Pair
对象组成的链表来表示边权值
w
的边
(
u
,
v
)
关于图的操作可以细分为如下几类:

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.