603 图的遍历

图的遍历

图的遍历是图论中的基本操作，主要有两种经典算法：深度优先遍历（DFS）和广度优先遍历（BFS）。这两种算法都可以通过邻接矩阵或邻接表来实现图的表示。

特性/算法	深度优先遍历 (DFS)	广度优先遍历 (BFS)
基本思想/搜索策略	尽可能深地搜索图的分支，直到到达末端，然后回溯。优先纵向深入。	从起始点开始，先访问所有邻近顶点，然后逐层向外扩展。优先横向展开。
数据结构	栈 (通过函数调用栈隐式使用递归，或显式使用栈)。	队列。
访问顺序特点	后进先出 (LIFO) 的特点，类似于树的先序遍历。	先进先出 (FIFO) 的特点，类似于树的层序遍历。
是否递归	通常是递归算法 (也可使用显式栈迭代实现)。	通常是非递归算法，使用队列迭代实现。
查找路径	能够找到路径，但不一定是最短路径。	在无权图中，可以找到从起点到其他所有可达顶点的最短路径 (按边数计)。
应用场景	拓扑排序、寻找路径、检测图有无环路、求解迷宫、寻找连通分量、二分图检测、强连通分量 (SCC) 求解 (如 Tarjan, Kosaraju 算法)。	无权图的最短路径问题、社交网络中查找一度或二度好友、层序遍历、网络爬虫、连通分量。
空间复杂度	$O(V)$ (递归栈的最大深度，最坏情况下为 $V$)。	$O(V)$ (队列中最多可能存储 $V$ 个顶点)。
时间复杂度 (邻接矩阵)	$O(V^2)$ (每个顶点都需要扫描一行/列以查找邻接点)。	$O(V^2)$ (每个顶点都需要扫描一行/列以查找邻接点)。
时间复杂度 (邻接表)	$O(V+E)$ (访问所有顶点和所有边)。	$O(V+E)$ (访问所有顶点和所有边)。
遍历结果唯一性	对于邻接矩阵通常唯一 (若按固定顺序选择邻接点)；对于邻接表不唯一。	对于邻接矩阵通常唯一；对于邻接表不唯一。

注：

• $V$ 表示图中顶点的数量。
• $E$ 表示图中边的数量。
• 时间复杂度和空间复杂度的分析是针对连通图的；对于非连通图，通常需要在外层加一个循环来确保所有顶点都被访问，但渐进复杂度不变。

深度优先遍历 (DFS)

深度优先遍历类似于树的先序遍历，它从图中的一个未访问顶点开始，沿着一条路径尽可能深地搜索图，直到到达路径的末端，然后回溯到前一个顶点，继续搜索其他路径。DFS 通常使用递归或显式栈来实现。

处理未连通图 如果图是未连通的，为了确保所有顶点都被访问，需要对图中的每个连通分量重复 DFS 过程。这通常通过一个循环来实现：遍历所有顶点，如果某个顶点尚未被访问，则从该顶点开始调用 DFS。

基于邻接矩阵的 DFS

算法描述:

1. 选择一个起始顶点 v，标记为已访问，并访问该顶点。
2. 查找邻接矩阵中 v 所在行，找到一个与 v 邻接且尚未被访问的顶点 w。
3. 如果找到这样的顶点 w，则从 w 开始递归执行 DFS。
4. 如果找不到这样的顶点（即 v 的所有邻接点都已被访问），则回溯到调用 v 的前一个顶点，继续此过程。
5. 重复以上步骤，直到图中所有与起始顶点连通的顶点都被访问。
6. 如果图中还有未被访问的顶点，则另选一个未被访问的顶点作为起始点，重复上述过程。

伪代码示例 (递归):

visited = array of booleans, initialized to false
DFS_Matrix(graph, v):
    mark v as visited
    process(v) // 访问顶点v
    for each vertex u from 0 to V-1: // 遍历所有可能的邻接点
        if graph.matrix[v][u] is an edge AND u is not visited:
            DFS_Matrix(graph, u)
 
// 主调用函数
DFSTraverse_Matrix(graph):
    for each vertex i in graph:
        visited[i] = false
    for each vertex i in graph:
        if i is not visited:
            DFS_Matrix(graph, i)

复杂度分析:

• 时间复杂度: $O(V^2)$，其中 $V$ 是顶点数。因为在遍历过程中，对于每个顶点，都需要扫描其在邻接矩阵中对应的整行（或列）以查找邻接点，这需要 $O(V)$ 的时间。由于有 $V$ 个顶点，总时间复杂度为 $O(V\times V)=O(V^2)$。
• 空间复杂度: $O(V)$。主要用于存储标记顶点是否被访问的 visited 数组，以及递归调用栈的深度（最坏情况下为 $V$）。

基于邻接表的 DFS

算法描述:

1. 选择一个起始顶点 v，标记为已访问，并访问该顶点。
2. 查找 v 的邻接表，找到一个与 v 邻接且尚未被访问的顶点 w。
3. 如果找到这样的顶点 w，则从 w 开始递归执行 DFS。
4. 如果 v 的邻接表中所有邻接点都已被访问，则回溯。
5. 重复以上步骤，直到图中所有与起始顶点连通的顶点都被访问。
6. 如果图中还有未被访问的顶点，则另选一个未被访问的顶点作为起始点，重复上述过程。

伪代码示例 (递归):

visited = array of booleans, initialized to false
DFS_List(graph, v):
    mark v as visited
    process(v) // 访问顶点v
    for each vertex u in graph.adjacency_list[v]:
        if u is not visited:
            DFS_List(graph, u)
 
// 主调用函数
DFSTraverse_List(graph):
    for each vertex i in graph:
        visited[i] = false
    for each vertex i in graph:
        if i is not visited:
            DFS_List(graph, i)

复杂度分析:

• 时间复杂度: $O(V+E)$，其中 $V$ 是顶点数， $E$ 是边数。每个顶点只被访问一次（入栈一次），这部分是 $O(V)$。在查找邻接点时，只需遍历当前顶点的邻接表。对于无向图，所有邻接表的总长度为 $2E$；对于有向图，为 $E$。因此，总时间复杂度为 $O(V+E)$。
• 空间复杂度: $O(V)$。用于 visited 数组和递归栈。

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

DFS 遍历图的过程可以隐式地构建一棵或多棵生成树（如果图不连通，则为生成森林）。

• 深度优先生成树 (DFS Tree)：在 DFS 遍历过程中，当第一次访问一个顶点 v 并从 v 递归调用访问其邻接点 w 时，边 $(v,w)$ 被称为树边 (Tree Edge)。所有树边构成的图就是深度优先生成树。
• 生成森林 (Spanning Forest)：如果图不连通，DFS 会从多个起始顶点开始遍历，每次遍历都会生成一棵深度优先生成树，这些树的集合就是深度优先生成森林。
• 边的分类：在 DFS 遍历过程中，除了树边，还可以识别出其他类型的边：
  • 回边 (Back Edge)：连接到当前顶点的祖先顶点的边。回边的存在表示图中存在环。
  • 前向边 (Forward Edge)：连接到当前顶点的非直接子孙的顶点的边，但在 DFS 树中是其子孙。
  • 交叉边 (Cross Edge)：连接到既不是当前顶点的祖先也不是其子孙的顶点的边。通常连接到已访问但未完成遍历的顶点，或已完成遍历的顶点。

广度优先遍历 (BFS)

广度优先遍历从图中的某个顶点出发，首先访问其所有相邻的顶点，然后访问这些相邻顶点的所有未被访问过的相邻顶点，依此类推，直到所有可达顶点都被访问。它通常使用队列来实现。BFS 类似于树的层序遍历。

处理未连通图 与 DFS 类似，如果图是未连通的，为了确保所有顶点都被访问，需要对图中的每个连通分量重复 BFS 过程。这通常通过一个循环来实现：遍历所有顶点，如果某个顶点尚未被访问，则从该顶点开始调用 BFS。

基于邻接矩阵的 BFS

算法描述:

1. 选择一个起始顶点 v，标记为已访问，并将其入队。
2. 当队列非空时，执行以下操作： a. 队头顶点 u 出队，并访问 u。 b. 查找邻接矩阵中 u 所在行，对于每一个与 u 邻接且尚未被访问的顶点 w，标记 w 为已访问，并将 w 入队。
3. 重复步骤 2，直到队列为空。
4. 如果图中还有未被访问的顶点，则另选一个未被访问的顶点作为起始点，重复上述过程。

伪代码示例:

BFS_Matrix(graph, start_node):
    visited = array of booleans, initialized to false
    queue = new empty queue
  
    mark start_node as visited
    queue.enqueue(start_node)
  
    while queue is not empty:
        u = queue.dequeue()
        process(u) // 访问顶点u
        for each vertex v from 0 to V-1: // 检查所有可能的邻接点
            if graph.matrix[u][v] is an edge AND v is not visited:
                mark v as visited
                queue.enqueue(v)
 
// 主调用函数
BFSTraverse_Matrix(graph):
    for each vertex i in graph:
        visited[i] = false
    for each vertex i in graph:
        if i is not visited:
            BFS_Matrix(graph, i) // 从i开始进行一次BFS

复杂度分析:

• 时间复杂度: $O(V^2)$。每个顶点入队出队一次。当一个顶点出队后，需要扫描邻接矩阵中它对应的一整行来找出所有未被访问的邻接点，这需要 $O(V)$ 的时间。由于有 $V$ 个顶点，总时间复杂度为 $O(V^2)$。
• 空间复杂度: $O(V)$。用于 visited 数组和队列（最坏情况下，队列可能存储接近 $V$ 个顶点）。

基于邻接表的 BFS

算法描述:

1. 选择一个起始顶点 v，标记为已访问，并将其入队。
2. 当队列非空时，执行以下操作： a. 队头顶点 u 出队，并访问 u。 b. 查找 u 的邻接表，对于每一个与 u 邻接且尚未被访问的顶点 w，标记 w 为已访问，并将 w 入队。
3. 重复步骤 2，直到队列为空。
4. 如果图中还有未被访问的顶点，则另选一个未被访问的顶点作为起始点，重复上述过程。

伪代码示例:

BFS_List(graph, start_node):
    visited = array of booleans, initialized to false
    queue = new empty queue
  
    mark start_node as visited
    queue.enqueue(start_node)
  
    while queue is not empty:
        u = queue.dequeue()
        process(u) // 访问顶点u
        for each vertex v in graph.adjacency_list[u]:
            if v is not visited:
                mark v as visited
                queue.enqueue(v)
 
// 主调用函数
BFSTraverse_List(graph):
    for each vertex i in graph:
        visited[i] = false
    for each vertex i in graph:
        if i is not visited:
            BFS_List(graph, i) // 从i开始进行一次BFS

复杂度分析:

• 时间复杂度: $O(V+E)$。每个顶点入队出队一次，这部分是 $O(V)$。在访问邻接点时，只需遍历当前顶点的邻接表。所有邻接表的总长度（即所有边的数量）在整个过程中被访问一次，这部分是 $O(E)$。因此，总时间复杂度为 $O(V+E)$。
• 空间复杂度: $O(V)$。用于 visited 数组和队列。

BFS 求解单源最短路径问题

在无权图中，BFS 可以用于求解从给定源点到所有其他可达顶点的最短路径（按边数计算）。

原理：BFS 逐层扩展的特性保证了它总是先访问距离源点更近的顶点。当一个顶点被第一次访问时，它与源点的距离就是最短的。

实现：

1. 在 visited 数组的基础上，增加一个 distance 数组，用于记录每个顶点到源点的最短距离，初始化为无穷大。源点距离为 0。
2. 当一个顶点 u 出队时，其所有未访问的邻接点 v 的距离设为 distance[u] + 1。

广度优先生成树

BFS 遍历图的过程也可以隐式地构建一棵或多棵生成树。

• 广度优先生成树 (BFS Tree)：在 BFS 遍历过程中，当第一次从队列中取出顶点 u，并将其未访问的邻接点 v 加入队列时，边 $(u,v)$ 被称为树边 (Tree Edge)。所有这些树边构成的图就是广度优先生成树。
• 生成森林 (Spanning Forest)：如果图不连通，BFS 会从多个起始顶点开始遍历，每次遍历都会生成一棵广度优先生成树，这些树的集合就是广度优先生成森林。
• 边的分类：在 BFS 遍历过程中，所有边都是树边或交叉边。没有回边和前向边，因为 BFS 的分层特性保证了不会访问到已访问过的祖先或子孙。

总结

无论是 DFS 还是 BFS，基于邻接表的实现通常在稀疏图（边数远小于 $V^2$）中效率更高，而基于邻接矩阵的实现在稠密图中表现相对稳定，但其 $O(V^2)$ 的时间复杂度在顶点数量大时可能成为瓶颈。

空间复杂度两者通常都是 $O(V)$。 值得注意的是，对于基于邻接表存储的图，DFS 和 BFS 遍历得到的顶点序列可能不唯一，取决于边的输入次序和邻接表的构造方式（例如，邻接表中顶点的顺序）。然而，基于邻接矩阵得到的遍历序列通常是唯一的（如果规定了按顶点编号从小到大等固定顺序选择下一个邻接点）。

图的遍历与图的联通性

图的遍历是判断图的连通性的基础。

连通性理论

• 连通图：对于无向图，如果从任意一个顶点出发进行一次完整的 DFS 或 BFS 遍历，能够访问到图中所有其他顶点，则该图是连通图。
• 连通分量：对于非连通图，通过多次 DFS 或 BFS 遍历（每次从一个未访问的顶点开始），可以找出图中的所有连通分量。每次从一个未访问顶点开始的遍历，都将访问到一个新的连通分量中的所有顶点。
• 强连通分量 (SCC)：对于有向图，DFS 尤其适用于寻找强连通分量（如 Tarjan 算法或 Kosaraju 算法），这些算法通常依赖于 DFS 遍历的性质（如完成时间、回边等）。BFS 通常不直接用于寻找强连通分量。