数据结构之图的遍历

图的遍历概述

图的遍历是指从图中的某一顶点出发，按照特定的搜索方法沿着图中的边访问所有顶点，且每个顶点仅访问一次。图的遍历可以用于解决连通性问题、拓扑排序和关键路径等问题。图的遍历比树的遍历要复杂，因为图的顶点可能存在环，导致遍历过程中可能再次访问同一顶点。因此，在遍历过程中需要记录已访问的顶点，通常使用一个辅助数组 visited[] 来标记。

广度优先搜索 (BFS)

基本思想

广度优先搜索（Breadth-First Search, BFS）是一种类似于二叉树层序遍历的图遍历方法。其基本步骤如下：

  1. 访问起始顶点 $ v $。
  2. 访问未被访问过的邻接顶点，依次将其入队列。
  3. 从队列中取出顶点，访问其所有未被访问的邻接顶点，直至所有顶点都被访问。
  4. 处理连通图: 如果图中仍有未访问的顶点，则选取一个未被访问的顶点作为新的起点，重复上述过程，直到所有顶点都被访问。

BFS 的实现需要一个辅助队列来存储正在访问的顶点的下一层顶点，以实现逐层访问。

BFS 伪代码

以下是广度优先搜索的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 访问标记数组
bool visited[MAX_VERTEX_NUM];

// 对图 G 进行广度优先遍历
void BFSTraverse(Graph G) {
    for (i = 0; i < G.vexnum; ++i) {
        visited[i] = FALSE; // 初始化访问标记
    }
    InitQueue(Q); // 初始化队列
    for (i = 0; i < G.vexnum; ++i) {
        if (!visited[i]) {
            BFS(G, i); // 对未访问的顶点进行 BFS
        }
    }
}

// 从顶点 v 开始广度优先遍历图 G
void BFS(Graph G, int v) {
    visit(v); // 访问初始顶点 v
    visited[v] = TRUE; // 标记顶点 v 为已访问
    Enqueue(Q, v); // 将顶点 v 入队列

    while (!isEmpty(Q)) { // 当队列不为空
        DeQueue(Q, v); // 从队列中出队顶点 v
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            // 检测 v 的所有邻接点
            if (!visited[w]) { // 如果 w 为未访问的邻接顶点
                visit(w); // 访问顶点 w
                visited[w] = TRUE; // 标记 w 为已访问
                Enqueue(Q, w); // 将 w 入队列
            }
        }
    }
}

BFS 代码实现的解释

  1. 初始化访问标记: 使用数组 visited[] 来记录每个顶点是否被访问过。
  2. 初始化队列: 使用队列来存储待访问的顶点。
  3. 遍历每个顶点: 依次检查图中的每个顶点，若未被访问，则从该顶点开始执行 BFS。
  4. 访问顶点: 访问当前顶点并将其标记为已访问，然后将其邻接的未访问顶点依次入队。
  5. 继续访问: 通过队列逐层访问每个顶点，直到所有可达的顶点都被访问。

BFS 算法性能分析

  • 时间复杂度：
    • 如果使用邻接表存储，时间复杂度为 $ O(V + E) $，其中 $ V $ 是顶点数，$ E $ 是边数。每个顶点和每条边都被访问一次。
    • 如果使用邻接矩阵存储，时间复杂度为 $ O(V^2) $，因为查找每个顶点的邻接点需要 $ O(V) $ 的时间。
  • 空间复杂度：
    • BFS 使用一个辅助队列和一个访问标记数组，因此空间复杂度为 $ O(V) $。

BFS 算法求解单源最短路径问题

在非带权图中，BFS 可以有效地求解从源顶点 $ u $ 到其他所有顶点的最短路径。路径的长度定义为从源顶点到目标顶点所经过的最小边数。

BFS 求解单源最短路径的算法伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BFS_MIN_Distance(Graph G, int u) {
    for (i = 0; i < G.vexnum; ++i) {
        d[i] = ∞; // 初始化路径长度
    }
    visited[u] = TRUE;
    d[u] = 0;  // 源顶点到自身的距离为0
    EnQueue(Q, u);

    while (!isEmpty(Q)) {
        DeQueue(Q, u);
        for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
            if (!visited[w]) {
                visited[w] = TRUE;  // 标记 w 为已访问
                d[w] = d[u] + 1;    // 路径长度加1
                EnQueue(Q, w);      // 将 w 入队
            }
        }
    }
}

在这个算法中，d[i] 表示从源顶点 $ u $ 到顶点 $ i $ 的最短路径长度。使用 BFS 时，路径长度始终按距离从源顶点向外扩展，确保找到的路径是最短的。

广度优先生成树 (BFS Tree)

在图的广度优先搜索过程中，可以构建出一棵生成树，这棵树称为广度优先生成树（BFS Tree）。广度优先生成树的构建过程与 BFS 的遍历过程密切相关，以下是关于广度优先生成树的详细说明。

概念

广度优先生成树是通过广度优先搜索算法从图中生成的一棵树，其包含了从起始顶点出发所能到达的所有顶点，以及它们之间的连接关系。在这棵树中，起始顶点是根节点，其他顶点则根据访问的顺序与起始顶点建立边。

  • 唯一性：
    • 邻接矩阵存储：如果图的存储方式为邻接矩阵，那么生成的广度优先生成树是唯一的。这是因为邻接矩阵明确地定义了顶点之间的连接关系，每次访问的邻接顶点是确定的。
    • 邻接表存储：如果图的存储方式为邻接表，生成的广度优先生成树可能是不唯一的。邻接表的顺序可能不同，导致 BFS 访问的顺序也不同，从而形成不同的生成树。

广度优先生成树的构建过程

构建广度优先生成树的过程可以通过以下步骤实现：

  1. 初始化：
    • 创建一个空的队列，用于存储待访问的顶点。
    • 初始化一个访问标记数组，标记哪些顶点已经被访问过。
    • 创建一棵树，根节点为起始顶点，并准备记录树的边。
  2. 访问顶点：
    • 将起始顶点入队，标记为已访问。
    • 当队列非空时：
      • 从队列中取出一个顶点 $ u $。
      • 遍历与 $ u $ 邻接的所有顶点 $ w $：
        • 如果 $ w $ 尚未被访问：
          • 将 $ w $ 标记为已访问。
          • 将 $ w $ 入队。
          • 在生成树中添加边 $ (u, w) $ 表示 $ w $ 是 $ u $ 的子节点。
  3. 结束条件：
    • 当队列为空时，算法结束，广度优先生成树构建完成。
image-20241008174126135

深度优先搜索 (DFS)

深度优先搜索（Depth-First Search, DFS）是一种图遍历算法，它的搜索策略是尽可能“深”地探索图中的节点。与广度优先搜索（BFS）不同，DFS 类似于树的先序遍历，其基本思想是：

  1. 访问起始顶点 \(v\)。
  2. 从 \(v\) 开始，访问与 \(v\) 邻接且尚未被访问的顶点 \(w\)。
  3. 重复以上步骤，直到没有未被访问的邻接顶点为止。
  4. 此时退回到最近访问过的顶点，继续探索其他未被访问的邻接顶点，直到图中所有顶点都被访问过。

DFS 算法

以下是 DFS 的递归实现伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 访问标记数组
bool visited[MAX_VERTEX_NUM];

// 对图 G 进行深度优先遍历
void DFS_Traverse(Graph G) {
    for (v = 0; v < G.vexnum; ++v) {
        visited[v] = FALSE; // 初始化访问标记
    }
    for (v = 0; v < G.vexnum; ++v) {
        if (!visited[v]) {
            DFS(G, v); // 如果尚未访问，则进行 DFS
        }
    }
}

void DFS(Graph G, int v) {
    // 访问顶点 v
    visit(v);
    visited[v] = TRUE; // 设置访问标记为 TRUE

    // 遍历与 v 邻接的未被访问的顶点
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w]) {
            DFS(G, w); // 递归访问邻接顶点
        }
    }
}

DFS 算法的性能分析

  • 空间复杂度：DFS 是一个递归算法，需要使用递归栈，空间复杂度为 $ O(h) $，其中 $ h $ 是图的深度（在最坏情况下，可能达到 $ O(V) $）。
  • 时间复杂度：
    • 使用邻接矩阵表示时：查找每个顶点的邻接点时间复杂度为 $ O(V) $，因此总的时间复杂度为 $ O(V^2) $。
    • 使用邻接表表示时：查找所有顶点的邻接点时间复杂度为 $ O(E) $，访问每个顶点的时间复杂度为 $ O(V) $，因此总的时间复杂度为 $ O(V + E) $。

深度优先生成树和生成森林

与广度优先搜索（BFS）一样，深度优先搜索（DFS）也会产生一棵深度优先生成树。这一特性在连通图中尤为明显。若对非连通图进行 DFS，生成的将是深度优先生成森林。

  • 深度优先生成树：在连通图中，由 DFS 生成的一棵树，包含了从起始顶点出发能到达的所有顶点。
  • 深度优先生成森林：在非连通图中，由 DFS 生成的多棵树的集合。

与 BFS 类似，基于邻接表存储的深度优先生成树是不唯一的，因为邻接表的遍历顺序可能影响 DFS 的结果。

image-20241008182043527

图的遍历与图的连通性

图的遍历算法可以有效地判断图的连通性。以下是无向图和有向图连通性判断的基本原理和方法。

1. 无向图的连通性

  • 连通图：如果一个无向图是连通的，则从任一顶点出发，仅需一次遍历（使用广度优先搜索 BFS 或深度优先搜索 DFS）即可访问图中的所有顶点。
  • 非连通图：如果无向图是非连通的，从某一个顶点出发的遍历仅能访问到该顶点所在的连通分量中的所有顶点，而无法访问其他连通分量的顶点。

示例：

  • 在无向图中，若存在多个连通分量，调用 BFS 或 DFS 的次数等于该图的连通分量数量。例如，在遍历过程中，如果访问到的某个顶点的所有邻接顶点均已被访问，且仍有未被访问的顶点，则需从这些未被访问的顶点中选择一个作为新的起始点，继续遍历。

2. 有向图的连通性

对于有向图，判断其连通性的标准更为复杂。主要有以下两种情况：

  • 强连通图：在强连通图中，从任意顶点出发，都能够通过有向路径到达图中的所有其他顶点。
  • 非强连通图：在非强连通图中，可能存在一些顶点无法通过有向路径从某一初始顶点到达。

示例：

  • 在有向图中，可能存在强连通分量和非强连通分量。对于非强连通分量，使用 BFS 或 DFS 进行遍历时，不能保证访问到该连通分量的所有顶点。

3. 遍历算法实现

在 BFS 和 DFS 的实现中，可以添加一个外部循环来遍历所有顶点，以确保所有顶点均能被访问。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BFS_Connect(Graph G) {
    for (int i = 0; i < G.vexnum; ++i) {
        if (!visited[i]) {
            BFS(G, i); // 从未访问的顶点开始 BFS
        }
    }
}

void DFS_Connect(Graph G) {
    for (int i = 0; i < G.vexnum; ++i) {
        if (!visited[i]) {
            DFS(G, i); // 从未访问的顶点开始 DFS
        }
    }
}

4. 图的连通性判断

  • 无向图：通过多次调用 BFS 或 DFS，若最终能够访问到所有顶点，则该图是连通的；否则，若有顶点未被访问，则该图为非连通图。
  • 有向图：需要针对每个强连通分量进行判断，若从某一顶点出发不能到达所有其他顶点，则该图为非强连通。

选择题

01. 下列关于广度优先算法的说法中，正确的是()

  1. 当各边的权值相等时，广度优先算法可以解决单源最短路径问题。
  2. 当各边的权值不等时，广度优先算法可用来解决单源最短路径问题。
  3. 广度优先遍历算法类似于树中的后序遍历算法。
  4. 实现图的广度优先算法时，使用的数据结构是队列。

选项：

  • A. I、IV
  • B. I、II、IV
  • C. I、IV
  • D. I、II、IV

答案： A

解释：

  • 选项 I： 正确。当各边的权值相等时，广度优先算法（BFS）确实可以用于解决单源最短路径问题，因为 BFS 会层层遍历，保证最先到达的顶点是最短路径。
  • 选项 II： 错误。当各边的权值不等时，广度优先算法不能保证找到最短路径。在这种情况下，Dijkstra 算法更适合解决单源最短路径问题。
  • 选项 III： 错误。广度优先遍历算法类似于树中的层序遍历，而不是后序遍历。
  • 选项 IV： 正确。实现广度优先算法时，需要使用队列数据结构，以确保按层次顺序访问顶点。

因此，正确的选项是 A（I、IV）。

02. 对于一个非连通无向图 G, 采用深度优先遍历访问所有顶点，在 DFSTraverse 函数中调用 DFS 的次数正好等于()。

  • A. 顶连通分量数
  • B. 边数
  • C. 连通分量数
  • D. 不确定

答案： C

解释：

  • 深度优先搜索（DFS）可用于计算图的连通分量数。在非连通无向图中，每次调用 DFS 函数时，都会访问一个连通分量的所有顶点。因此，DFSTraverse() 中 DFS 被调用的次数正好等于图的连通分量数。

03. 对于一个有 n 个顶点、e 条边的图采用邻接表表示时，进行 DFS 遍历的时间复杂度为()，空间复杂度为()。进行 BFS 遍历的时间复杂度为()，空间复杂度为()。

  • A. O(n)
  • B. O(e)
  • C. O(n + e)
  • D. O(1)

答案：

  • 时间复杂度：C (O(n + e))
  • 空间复杂度：A (O(n)) (对于 DFS，O(n) 是存储递归栈的空间复杂度；对于 BFS，O(n) 是存储队列的空间复杂度)

解释：

  • 在邻接表表示的图中，DFS 和 BFS 的时间复杂度均为 O(n + e)，其中 n 是顶点数，e 是边数，因为需要访问每个顶点和每条边一次。空间复杂度为 O(n)，因为需要额外的空间存储顶点状态（访问标记）和栈/队列。

04. 对于有 n 个顶点、e 条边的图采用邻接矩阵表示时，进行 DFS 遍历的时间复杂度为()，进行 BFS 遍历的时间复杂度为()。

  • A. O(n^2)
  • B. O(e)
  • C. O(n + e)
  • D. O(e)

答案：

  • DFS 时间复杂度：A (O(n^2))
  • BFS 时间复杂度：A (O(n^2))

解释：

  • 使用邻接矩阵表示图时，查找一个顶点所有出边的时间复杂度为 O(n)。因此，无论是 DFS 还是 BFS，在邻接矩阵中都需对每个顶点进行 O(n) 的检查，整体复杂度为 O(n^2)。

05. 对无向图 G= (V,E)，其中 V= {a,b,c,d,e,f}，E= {(a,b), (a,e), (a,c), (b,e), (c,d), (f,d), (e,d)}，对该图从 a 开始进行深度优先遍历，得到的顶点序列正确的是()。

  • A. a, b, e, c, d, f
  • B. a, c, f, e, b, d
  • C. a, e, d, f, c, b
  • D. a, e, d, f,c, b

答案： D

解释：

排除法即可。

06. 如下图所示，在下面的5个序列中，符合深度优先遍历的序列个数是( )。

  1. aebfdc
  2. acfdeb
  3. aedfcb
  4. aefdbc
  5. aecfdb
  • A. 5
  • B. 4
  • C. 3
  • D. 2
image-20241008190450641

答案： D

解释：

  • 符合深度优先遍历（DFS）的序列应遵循先访问当前节点，再递归访问未被访问的邻接节点的原则。
  • aebfdc：有效，按照顺序访问了 a -> e -> b -> f -> d -> c。
  • acfdeb：无效，c 应该在 b 之前被访问到。
  • aedfcb：有效，按照顺序访问了 a -> e -> d -> f -> c -> b。
  • aefdbc：无效，f 应该在 b 之前被访问到。
  • aecfdb：无效，c 不应在 e 之后被访问到。

综上，符合深度优先遍历的序列为 1 和 3，因此总个数为 2。

07. 用邻接表存储的图的深度优先遍历算法类似于树的( )，而其广度优先遍历算法类似于树的( )。

  • A. 中序遍历
  • B. 先序遍历
  • C. 后序遍历
  • D. 按层次遍历

答案： B、D

解释：

  • 图的深度优先遍历（DFS）算法类似于树的 先序遍历（先访问当前节点，然后遍历子节点）。深度优先遍历使用回溯的方式，可以看作是递归地深入每一个分支。
  • 图的广度优先遍历（BFS）算法类似于树的 按层次遍历（逐层访问树的每一层节点），利用队列的方式实现逐层扩展。

08. 一个有向图 G 的邻接表存储如下图所示，从顶点 1 出发，对图 G 调用深度优先遍历所得顶点序列是();按广度优先遍历所得顶点序列是()。

  • A. 125436
  • B. 124536
  • C. 124563
  • D. 362514
image-20241008190501516

答案： A、B

解释：

DFS 序列产生的路径为\(<1,2>,<2.5>,<5,4>,<3,6>\);BFS 序列产生的路径为\(<1,2>,<1,4>,<25>, <3, 6>\)。

09. 无向图 G=(V,E)，其中 V={a, b, c, d, e}，E={(a,b),(a,e),(a,c),(b,e),(c,d),(e,d)}。对该图进行深度优先遍历，不能得到的序列是()

  • A. acfdeb
  • B. aebdfc
  • C. aedfcb
  • D. abecdf

答案： D

解释：

  • 给定的无向图 G 的邻接关系可以表示为：

    1
    2
    3
    4
    5
    6
    a - b
    a - e
    a - c
    b - e
    c - d
    e - d

  • 进行深度优先遍历时，可能的访问序列取决于遍历时访问邻接点的顺序。

  • 对于选项分析：

    • A. acfdeb：有效，符合深度优先遍历的规则。
    • B. aebdfc：有效，符合深度优先遍历的规则。
    • C. aedfcb：有效，符合深度优先遍历的规则。
    • D. abecdf：无效，深度优先遍历过程中，从 a 访问 b 后，访问 e 后应该返回到 d，然后才可以访问 c。

所以，选项 D 是不可能的。

10. 判断有向图中是否存在回路，除可以利用拓扑排序外，还可以利用()

  • A. 求关键路径的方法
  • B. 求最短路径的 Dijkstra 算法
  • C. 深度优先遍历算法
  • D. 广度优先遍历算法

答案： C

解释：

  • 判断有向图是否存在回路的方法包括：
    • 拓扑排序：如果图能够进行拓扑排序，则图中无环。
    • 深度优先遍历（DFS）：在深度优先遍历过程中，如果遇到回边（即当前节点指向已在递归栈中的节点），则图中存在回路。
    • 选项 A 和 B 不直接用于判断回路的存在性，而选项 D 广度优先遍历通常不用于判断回路。

因此，正确答案是 C。

11. 使用 DFS 算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是()

  • A. 逆拓扑有序
  • B. 拓扑有序
  • C. 无序的
  • D. 都不是

答案： A

解释：

  • 对于无环有向图（DAG）使用深度优先遍历（DFS）时，在退出递归（回溯）时输出顶点，可以得到一个 逆拓扑序列。在完成所有后继节点的访问后，当前节点的输出顺序恰好是逆序的。

12. 设无向图 G=(V,E)和 G'=(V,E')，若 G' 是 G 的生成树，则下列说法中错误的是( )。

  • A. G 为 G 的子图
  • B. G' 为 G 的连通分量
  • C. G' 为 G 的极小连通子图且 V=V'
  • D. G' 是 G 的一个无环子图

答案： B

解释：

  • 生成树是连接图中所有顶点的无环子图，因此：
    • A. G 为 G 的子图：正确，生成树是原图的子图。
    • B. G' 为 G 的连通分量：错误，连通分量是无向图的极大连通子图，而 G' 是 G 的一个特定子图，可能是一个连通图，但不一定是连通分量。
    • C. G' 为 G 的极小连通子图且 V=V'：正确，生成树包含图的所有顶点，并且是极小连通的。
    • D. G' 是 G 的一个无环子图：正确，生成树本质上是无环的。

因此，答案是 B。

13. 图的广度优先生成树的树高比深度优先生成树的树高()。

  • A. 小或相等
  • B. 小
  • C. 大或相等
  • D. 大

答案： A

解释：

  • 广度优先搜索（BFS）生成的树是最短路径树，因为它从起点出发，优先访问距离起点最近的节点，因此其高度（从根到最深叶子节点的最长路径）通常是最小的。
  • 相对而言，深度优先搜索（DFS）会尽可能深入地探索分支，可能会导致更长的路径，从而使得生成树的高度较大。
  • 因此，广度优先生成树的树高要么小于，或者在特定情况下等于深度优先生成树的树高。

14. 对有 n 个顶点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是( )。

  • A. $ O(n) $
  • B. $ O(e) $
  • C. $ O(n + e) $
  • D. $ O(ne) $

答案： C

解释：

  • 在使用邻接表进行广度优先遍历时：
    • 每个顶点在入队时只会被访问一次，因此对所有 n 个顶点的遍历时间为 $ O(n) $。
    • 对于每条边，在遍历邻接表时，每条边会被访问一次，因此对于所有 e 条边的遍历时间为 $ O(e) $。
  • 综合起来，广度优先遍历的总时间复杂度为 $ O(n + e) $。

15. 若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是()。

  • A. h, c, a, b, d, e, g, f
  • B. e, a, f, g, b, h, c, d
  • C. d, b, c, a, h, e, f,g
  • D. a, b, c, d, h, e, f, g
image-20241008191632776

答案： D

解释：

  • 广度优先遍历（BFS）从某个起始节点出发，首先访问所有直接相邻的节点，然后再访问这些相邻节点的相邻节点，依此类推。
  • 对于每个选项进行分析：
    • A：符合BFS的遍历顺序。
    • B：符合BFS的遍历顺序。
    • C：符合BFS的遍历顺序。
    • D：是深度优先遍历，而不是广度优先遍历。是深度优先遍历，而不是广度优先遍历。

因此，选项 D 不是广度优先遍历的有效序列。

16. 设有向图 $ G=(V,E) $，顶点集 $ V= {v_0,v_1,v_2,v_3} $，边集 $ E= {(v_0,v_1),(v_1,v_2),(v_2,v_3),(v_1,v_3)} $。若从顶点 $ v_0 $ 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是()。

  • A. 2
  • B. 3
  • C. 4
  • D. 5

答案： D

image-20241008192022953

17. 下列选项中，不是下图深度优先搜索序列的是()。

image-20241008192046308

答案： D(\(V_1,V_2,V_3,V_4,V_5\))

解释：

模拟即可。

程序解答题

01. 图 $ G = (V, E) $ 以邻接表存储，如下图所示。试画出图 $ G $ 的深度优先生成树和广度优先生成树（假设从节点 1 开始遍历）。

image-20241008192312965
image-20241008192325367

02. 设计一个算法，判断一个无向图 $ G $ 是否为一棵树。若是一棵树，则算法返回 true，否则返回 false。

解答

一个无向图 $ G $ 是一棵树的条件是：

  1. $ G $ 必须是连通的。
  2. $ G $ 必须无回路。
  3. 如果 $ G $ 有 $ n $ 个顶点，则它必须有 $ n-1 $ 条边。

这里采用后者作为判断条件。可以使用深度优先搜索（DFS）算法来判断图的连通性，同时统计顶点数和边数。具体实现如下：

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>

using namespace std;

struct Graph {
    int vexnum; // 顶点数
    vector<vector<int>> adj; // 邻接表
};

// 深度优先搜索
void DFS(Graph& G, int v, int& Vnum, int& Enum, vector<bool>& visited) {
    visited[v] = true; // 标记为已访问
    Vnum++; // 统计访问的顶点数
    int w = 0; // 邻接顶点

    for (int i = 0; i < G.adj[v].size(); i++) {
        w = G.adj[v][i]; // 获取邻接顶点
        if (w != -1) { // 邻接顶点存在
            Enum++; // 统计边数
            if (!visited[w]) { // 如果未访问过
                DFS(G, w, Vnum, Enum, visited); // 递归访问
            }
        }
    }
}

// 判断图是否为树
bool isTree(Graph& G) {
    vector<bool> visited(G.vexnum, false); // 访问标记初始化
    int Vnum = 0; // 访问的顶点数
    int Enum = 0; // 访问的边数

    DFS(G, 0, Vnum, Enum, visited); // 从第一个顶点开始 DFS

    // 判断是否符合树的条件
    if (Vnum == G.vexnum && Enum == 2 * (G.vexnum - 1)) {
        return true; // 符合树的条件
    } else {
        return false; // 不符合树的条件
    }
}

解释

  1. 图的结构：图使用邻接表表示。Graph 结构体包含顶点数 vexnum 和邻接表 adj。
  2. 深度优先搜索（DFS）：DFS 函数在访问过程中统计访问的顶点数 Vnum 和边数 Enum。每次访问一个顶点时，标记为已访问，并对其所有邻接顶点进行递归访问。
  3. 判断条件：
    • Vnum 应等于图的顶点数 G.vexnum，表示图是连通的。
    • Enum 应等于 2 * (G.vexnum - 1)，这是因为无向图中每条边被访问两次（一次从每个端点访问），这确保了图没有回路。

03. 写出图的深度优先搜索（DFS）算法的非递归实现（图采用邻接表形式）。

解答

在深度优先搜索的非递归算法中，使用了一个栈来记忆下一步可能访问的顶点，同时使用一个访问标记数组 visited[i] 来记忆第 $ i $ 个顶点是否在栈内或曾经在栈内，若是则它以后不能再进栈。以下是图的非递归深度优先搜索算法的实现：

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct Graph {
    int vexnum; // 顶点数
    vector<vector<int>> adj; // 邻接表
};

// 非递归深度优先搜索
void DFS_NonRecursive(Graph& G, int v) {
    vector<bool> visited(G.vexnum, false); // 访问标记初始化
    stack<int> S; // 定义栈
    int w; // 邻接顶点

    // 将起始顶点入栈并标记为已访问
    S.push(v);
    visited[v] = true;

    while (!S.empty()) {
        // 栈中退出一个顶点
        int k = S.top();
        S.pop();

        // 访问当前顶点
        cout << "Visited: " << k << endl;

        // 遍历当前顶点的所有邻接顶点
        for (w = 0; w < G.adj[k].size(); w++) {
            int neighbor = G.adj[k][w]; // 获取邻接顶点
            // 如果邻接顶点未被访问
            if (!visited[neighbor]) {
                // 将其入栈并标记为已访问
                S.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

解释

  1. 图的结构：图使用邻接表表示。Graph 结构体包含顶点数 vexnum 和邻接表 adj。

  2. 非递归 DFS 的步骤：

    • 栈的初始化：首先创建一个栈 S，并将起始顶点 $ v $ 入栈，标记为已访问。
    • 遍历：在栈非空的情况下，重复以下操作：
      • 从栈中弹出一个顶点 $ k $，并访问该顶点（打印或处理）。
      • 遍历顶点 $ k $ 的所有邻接顶点。
      • 对于每个邻接顶点，如果未被访问，则将其入栈并标记为已访问。

  3. 访问顺序：由于栈的后进先出特性，非递归 DFS 将从当前顶点的右邻接顶点开始访问，依次访问左邻接顶点。这与递归 DFS 的访问顺序可能会略有不同。

04. 分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中，是否存在从顶点 $ v_i $ 到顶点 $ v_j $ 的路径。

解答

为了判断一个有向图中是否存在从顶点 $ v_i $ 到顶点 $ v_j $ 的路径，可以使用深度优先遍历（DFS）和广度优先遍历（BFS）两种算法。以下是这两种算法的实现：

1. 深度优先遍历（DFS）

深度优先遍历用于判断从顶点 $ v_i $ 到顶点 $ v_j $ 是否有路径的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void DFS(ALGraph G, int i, int j, bool &can_reach, int visited[]) {
    if (i == j) {
        can_reach = true; // 找到路径
        return;
    }

    visited[i] = 1; // 标记当前顶点为已访问

    for (int p = FirstNeighbor(G, i); p >= 0; p = NextNeighbor(G, i, p)) {
        if (!visited[p] && !can_reach) { // 如果邻接点未访问且尚未找到路径
            DFS(G, p, j, can_reach, visited); // 递归访问邻接点
        }
    }
}
  • 参数说明：
    • G: 有向图。
    • i: 当前顶点。
    • j: 目标顶点。
    • can_reach: 布尔变量，指示是否找到路径。
    • visited[]: 访问标记数组。

2. 广度优先遍历（BFS）

广度优先遍历用于判断从顶点 $ v_i $ 到顶点 $ v_j $ 是否有路径的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int BFS(ALGraph G, int i, int j) {
    int visited[MAXSIZE] = {0}; // 访问标记数组
    Queue Q; // 队列用于BFS
    InitQueue(Q); // 初始化队列
    EnQueue(Q, i); // 将起始顶点入队
    visited[i] = 1; // 标记起始顶点为已访问

    // 非空循环
    while (!isEmpty(Q)) {
        int u;
        DeQueue(Q, u); // 出队顶点

        if (u == j) return 1; // 找到目标顶点

        for (int p = FirstNeighbor(G, u); p >= 0; p = NextNeighbor(G, u, p)) {
            // 检查所有邻接点
            if (!visited[p]) { // 如果邻接点未被访问
                EnQueue(Q, p); // 入队
                visited[p] = 1; // 标记为已访问
            }
        }
    }

    return 0; // 未找到路径
}
  • 参数说明：
    • G: 有向图。
    • i: 当前顶点。
    • j: 目标顶点。

问题

05. 假设图用邻接表表示，设计一个算法，输出从顶点 $ V $ 到顶点 $ u $ 的所有简单路径。

解答

要输出从顶点 $ u $ 到顶点 $ v $ 的所有简单路径，可以采用基于递归的深度优先遍历（DFS）算法。以下是算法的详细实现和解释：

算法设计

  1. 递归函数 FindPath(G, u, v, path, d)：
    • 参数说明：
      • G: 图的邻接表表示。
      • u: 当前顶点。
      • v: 目标顶点。
      • path[]: 存放当前路径的数组。
      • d: 当前路径的长度（即路径中节点的数量）。
  2. 步骤：
    • 将当前顶点 $ u $ 添加到路径数组中。
    • 如果当前顶点 $ u $ 是目标顶点 $ v $，则输出当前路径。
    • 否则，遍历所有与 $ u $ 相邻的未访问过的顶点，递归调用 FindPath。
    • 在返回之前，将当前顶点标记为未访问，以便其他路径可以再次访问它。

算法实现

以下是该算法的 C++ 代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
using namespace std;

const int MAXSIZE = 100; // 假设最大顶点数为100
int visited[MAXSIZE]; // 访问标记数组

struct ArcNode {
    int adjvex; // 邻接顶点
    ArcNode* nextarc; // 指向下一个邻接点
};

struct AGraph {
    ArcNode* adjlist[MAXSIZE]; // 邻接表
    int vexnum; // 顶点数
};

// 打印路径
void printPath(int path[], int d) {
    for (int i = 0; i <= d; i++) {
        cout << path[i] << " ";
    }
    cout << endl;
}

// 查找从顶点u到顶点v的所有简单路径
void FindPath(AGraph* G, int u, int v, int path[], int d) {
    ArcNode* p;
    d++;
    path[d] = u; // 将当前顶点添加到路径中
    visited[u] = 1; // 标记为已访问

    if (u == v) { // 找到一条路径
        printPath(path, d); // 输出路径
    } else {
        p = G->adjlist[u]; // 获取u的第一个相邻点
        while (p != NULL) { // 遍历邻接点
            int w = p->adjvex; // 邻接顶点
            if (visited[w] == 0) { // 如果未访问
                FindPath(G, w, v, path, d); // 递归访问
            }
            p = p->nextarc; // 指向下一个邻接点
        }
    }

    visited[u] = 0; // 恢复状态，标记为未访问
}

int main() {
    // 示例代码：初始化图并调用FindPath函数（略）
    return 0;
}

说明

  1. 访问标记数组 visited[]：用于跟踪已访问的顶点，防止重复访问。
  2. 路径数组 path[]：存储当前路径，路径中的每个节点的索引为 0 到 $ d \(（\) d $ 是路径的长度）。
  3. 递归遍历：从顶点 $ u $ 开始，递归访问所有未访问的相邻节点，并在找到目标节点 $ v $ 时输出路径。

复杂度分析

  • 时间复杂度：最坏情况下，算法会遍历所有可能的路径，因此时间复杂度为 $ O(V + E) $，其中 $ V $ 是顶点数，$ E $ 是边数。
  • 空间复杂度：空间复杂度主要由递归调用的栈空间和路径数组占用，通常为 $ O(V) $。