算法技术手册（原书第2 版）

图算法

｜

131

图算法

创建图

图可以由

n

个顶点的集合初始构成，它可以是有向的，也可以是无向的。如果是无

向图，那么添加边

(

u

,

v

)

的同时也会添加边（

v

,

u

）。

查询图

我们可以判断图是否有向、找出某个给定顶点的所有关联边、判断某条边是否存在

以及查询某条边的权值；还可以创建一个迭代器，返回图中任一顶点的邻边（及其

权值）。

更新图

我们可以在图中添加边（或删除边）。当然，添加顶点（或者删除顶点）也是可行的，

只不过本章介绍的算法并不需要这类操作。

我们将通过介绍图遍历的若干方式展开讨论。图遍历的两种常见策略是

深度优先搜索

和

广度优先搜索

。

6.2 深度优先搜索

如图

6-5

所示，对于左边的迷宫，通过一些尝试，一个孩子可以快速地找到从框标签为

s

的起点到框标签为

t

的终点的一条路径。解决这个问题的一种方法是尽可能地向前移动，

并且只要可以，随机选择一个方向，然后标记从哪里进入。如果走入一条死路或者遇到

之前见过的地方，那么就不断回退，直到发现没有到过的分支上。图

6-5

右边的数字展

示了这样的解决方案所经过的分支点。事实上，在这个解中，我们访问了迷宫中的所有点。

图 6-5：从

s

到

t

的一个小型迷宫

我们可以创建一个包含点和边的图来表示图

6-5

所示的迷宫，其中顶点表示迷宫中的每

个分支点（在图

6-5

的右边用数字标记），当然也包括“死路点”。如果迷宫中在两个

顶点之间存在一条有向路，并且在这个方向上没有其他选择，那么就认为它们之间存在

一条边。图

6-5

中迷宫的无向图表示如图

6-6

所示，其中每个顶点都有一个唯一的标识符。