本章将介绍图的表示和图的搜索。图的搜索指的是系统化地跟随图中的边来访问图中的每个结点。图搜索算法可以用来发现图的结构。许多的图算法在一开始都会先通过搜索来获得图的结构，其他的一些图算法则是对基本的搜索加以优化。可以说，图的搜系技巧是整个图算法领域的核心。

• 22.1节对图的两种最常见的计算机表示法进行讨论。这两种表示法分别是邻接链表和邻接矩阵。
• 22.2节讲解一种简单的图搜索算法，称为广度优先搜索，并演示如何创建一棵广度优先树。
• 22.3节讲解深度优先搜索，同时对此种搜索所访问的结点之间的次序进行讨论，并对这方面的一些标准结果进行证明。
• 22.4节给出深度优先搜索的一个实际应用有向无环图中的拓扑排序。
• 22.5节则讨论深度优先搜索的另一个实际应用:在有向图中计算强连通分量。

22.1 图的表示

稀疏图 稠密图

邻接链表表示

图 22-1 无向图的两种表示

图 22-1 有向图的两种表示

权重图 权重 权重函数

邻接链表的一个潜在缺陷是无法快速判断一条边(u，v)是否是图中的一条边，唯一的办法是在邻接链表Adj[u]里面搜索结点v。邻接矩阵表示则克服了这个缺陷，但付出的代价是更大的存储空间消耗(存储空间的渐近数量级更大)(关于如何在邻接链表上进行快速边搜索的信息，请参阅练习22.1-8)。

邻接矩阵表示

表示图的属性

练习

22.1-6

大多数以邻接矩阵表示为输入的图算法需要时间Ω（V^2），但也有一些例外。演示如何确定有向图G是否包含通用接收器− 有度的顶点∣V∣−1和0度− 在时间O（V）中，给出G的邻接矩阵。

Solution

首先检查邻接矩阵中的位置（1,1）。检查位置（i，j）时，

如果遇到1，检查位置（i+1，j）和

如果遇到0，检查位置（i，j+1）。

一旦i或j等于∣V∣, 终止

IS-CONTAIN-UNIVERSAL-SINK(M)
    i = j = 1
    while i < |V| and j < |V|
        // There's an out-going edge, so examine the next row
        if M[i, j] == 1
            i = i + 1
        // There's no out-going edge, so see if we could reach the last column of current row
        else if M[i, j] == 0
            j = j + 1
    check if vertex i is a universal sink

如果一个图包含一个通用接收器，那么它必须在顶点i处。

要看到这一点，假设顶点k是一个通用接收器。由于k是一个通用接收器，k行将用0填充，k列将用1填充，M[k，k]除外，M[k，k]用0填充。最后，一旦命中行k，算法将继续增加列j直到j=∣V∣.

为了确保最终命中行k，请注意，一旦到达列k，算法将继续递增i，直到到达k为止。

该算法在O（V）中运行，并在O（V）中检查顶点i是否为通用接收器。因此，总运行时间为O（V）+O（V）=O（V）。