【c++高阶DS】图的遍历

🔥个人主页：Quitecoder

🔥专栏：c++笔记仓

01.图的遍历

给定一个图G和其中任意一个顶点v0，从v0出发，沿着图中各边访问图中的所有顶点，且每个顶点仅被遍历一次。"遍历"即对结点进行某种操作

广度优先

比如现在要找东西，假设有三个抽屉，东西在那个抽不清楚，现在要将其找到，广度优先遍历的做法是:
1.先将三个抽屉打开，在最外层找一遍
2.将每个抽屉中红色的盒子打开，再找一遍
3.将红色盒子中绿色盒子打开，再找一遍
直到找完所有的盒子，注意:每个盒子只能找一次，不能重复找

问题：如何防止节点被重复遍历

---

基本思路

1. 初始化：
   • 创建一个队列，用于记录待访问的顶点。
   • 创建一个数组或集合，用于标记已经访问过的顶点。
2. 从起始顶点开始：
   • 将起始顶点加入队列，同时标记为已访问。
3. 开始遍历：
   • 只要队列不为空，重复以下步骤：
     • 从队列中取出一个顶点，称为当前顶点。
     • 遍历当前顶点的所有邻居：
       • 如果某个邻居尚未被访问，则将其加入队列，并标记为已访问。
4. 结束条件：
   • 当队列为空时，遍历结束。

---

void BFS(const V& src)
{size_t srci = GetVertexIndex(src);vector<bool> visited;visited.resize(_vertexs.size(), false);queue<int> q;q.push(srci);visited[srci] = true;while (!q.empty()){int front = q.front();q.pop();cout << front << ":" << _vertexs[front] << endl;//把front的邻接顶点入队列for (int i = 0; i < _vertexs.size(); i++){if (_matrix[front][i] != MAX_W && visited[i] == false){visited[i] = true;q.push(i);}}}
}

---

详细步骤与例子

假设图如下（无向图）：

A -- B -- C
|    |
D -- E

图的邻接表表示：

A: B, D
B: A, C, E
C: B
D: A, E
E: B, D

从顶点 A 开始的广度优先遍历

1. 初始化：

   • 队列：q = [A]
   • 已访问集合：visited = {A}

2. 第一轮：

   • 从队列取出 A，访问 A。
   • 遍历 A 的邻居 B 和 D：
     • 将 B 和 D 加入队列：q = [B, D]
     • 标记 B 和 D 为已访问：visited = {A, B, D}

3. 第二轮：

   • 从队列取出 B，访问 B。
   • 遍历 B 的邻居 A、C、E：
     • A 已访问，跳过。
     • 将 C 和 E 加入队列：q = [D, C, E]
     • 标记 C 和 E 为已访问：visited = {A, B, D, C, E}

4. 第三轮：

   • 从队列取出 D，访问 D。
   • 遍历 D 的邻居 A、E：
     • A 和 E 已访问，跳过。

5. 第四轮：

   • 从队列取出 C，访问 C。
   • 遍历 C 的邻居 B：
     • B 已访问，跳过。

6. 第五轮：

   • 从队列取出 E，访问 E。
   • 遍历 E 的邻居 B、D：
     • B 和 D 已访问，跳过。

7. 结束：

   • 队列为空，遍历完成。

遍历顺序：
A -> B -> D -> C -> E

---

关键点

1. 队列的作用：

   • 保证顶点按层次顺序访问（即先访问距离起点较近的顶点，再访问较远的顶点）。

2. 访问标记的作用：

   • 防止重复访问顶点，避免死循环。例如，在无向图中，访问 A 时会发现 B，然后访问 B 时会发现 A，没有标记的话会导致无限循环。

3. 适用图的存储结构：

   • 邻接表：遍历顶点的邻居时高效。
   • 邻接矩阵：需要遍历整行寻找邻居，效率稍低。

4. 时间复杂度：

   • 对于邻接表表示的图：
     • 时间复杂度：$O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。
     • 遍历所有顶点需要 $O(V)$，遍历每个顶点的所有邻居需要 $O(E)$。
   • 对于邻接矩阵表示的图：
     • 时间复杂度：$O(V^2)$，因为需要检查矩阵中的每个元素。

5. 空间复杂度：

   • 主要由队列和访问标记占用，复杂度为 $O(V)$。

深度优先

比如现在要找东西，假设有三个抽屉，东西在那个抽屉不清楚，现在
要将其找到，广度优先遍历的做法是:

1. 先将第一个抽屉打开，在最外层找一遍

2. 将第一个抽屉中红盒子打开，在红盒子中找一遍

3. 将红盒子中绿盒子打开，在绿盒子中找一遍

4. 递归查找剩余的两个盒子

深度优先遍历:将一个抽屉一次性遍历完(包括该抽屉中包含的小盒
子)，再去递归遍历其他盒子

void _DFS(size_t srci,vector<bool> & visited)
{cout << srci << ":" << _vertexs[src] << " ";visited[srci] = true;for (int i = 0; i < _vertexs.size(); i++){if (_matrix[srci][i] != MAX_W && visited[i] == false){_DFS(i, visited);}}
}
void DFS(const V& src)
{size_t srci = GetVertexIndex(src);vector<bool> visited(_vertexs.size(), false);_DFS(src, visited);
}

---

深度优先遍历的特点

1. 优先深入：每次选择一个尚未访问的邻居节点递归访问，直到没有未访问的邻居为止。
2. 回溯策略：当某节点的所有邻居都被访问后，回溯到其上一个节点，继续探索其未访问的邻居。
3. 递归实现或使用栈：DFS 可以通过递归或显式栈来实现。
4. 标记节点：需要记录哪些节点已经被访问过，以避免重复访问或陷入死循环。

---

基本思路

1. 初始化

• 创建一个访问标记的数组或集合，用于记录已访问的顶点。
• 从起始顶点开始，将其标记为已访问，然后递归或借助栈访问其邻居。

2. 递归实现

• 对于每个顶点，访问其第一个未访问的邻居。
• 如果该邻居存在，递归调用深度优先遍历函数继续访问其邻居。
• 如果该顶点的所有邻居都被访问过，则回溯到上一层。

3. 使用显式栈

• 使用栈模拟递归的行为：
  • 初始时，将起始顶点入栈。
  • 每次从栈中取出顶点，访问该顶点，并将其所有未访问的邻居依次压入栈。

---

非递归实现（使用栈）

void DFS(Graph& graph, const V& start) {stack<V> s;                // 栈用于存储待访问的顶点unordered_set<V> visited;  // 标记已访问顶点s.push(start);             // 将起始顶点压入栈while (!s.empty()) {V current = s.top();   // 取出栈顶顶点s.pop();if (visited.find(current) == visited.end()) {// 标记当前顶点为已访问visited.insert(current);// 处理当前顶点（例如打印）cout << current << " ";// 将未访问的邻居压入栈for (const auto& neighbor : graph.GetNeighbors(current)) {if (visited.find(neighbor) == visited.end()) {s.push(neighbor);}}}}
}

---

详细过程与示例

假设图如下（无向图）：

A -- B -- C
|    |
D -- E

邻接表表示：

A: B, D
B: A, C, E
C: B
D: A, E
E: B, D

从顶点 A 开始的深度优先遍历

1. 递归实现

初始状态：

• 访问标记：visited = {}

遍历过程：

1. 访问顶点 A，标记为已访问：visited = {A}
2. 从 A 的邻居中选择未访问的 B，递归进入顶点 B：
   • 访问顶点 B，标记为已访问：visited = {A, B}
   • 从 B 的邻居中选择未访问的 C，递归进入顶点 C：
     • 访问顶点 C，标记为已访问：visited = {A, B, C}
     • C 的邻居 B 已访问，递归返回到顶点 B。
   • 返回到 B，继续访问其未访问的邻居 E，递归进入顶点 E：
     • 访问顶点 E，标记为已访问：visited = {A, B, C, E}
     • 从 E 的邻居中选择未访问的 D，递归进入顶点 D：
       • 访问顶点 D，标记为已访问：visited = {A, B, C, D, E}
       • D 的邻居 A、E 均已访问，递归返回到顶点 E。
     • 返回到 E，无更多未访问的邻居。
   • 返回到 B，无更多未访问的邻居。
3. 返回到 A，继续访问其未访问的邻居 D：
   • D 已访问，跳过。

最终结果：A -> B -> C -> E -> D

---

2. 非递归实现

初始状态：

• 栈：s = [A]
• 访问标记：visited = {}

遍历过程：

1. 从栈中弹出顶点 A，访问 A：visited = {A}，将邻居 B 和 D 压入栈：

   • 栈：s = [B, D]

2. 从栈中弹出顶点 D，访问 D：visited = {A, D}，将邻居 E 压入栈：

   • 栈：s = [B, E]

3. 从栈中弹出顶点 E，访问 E：visited = {A, D, E}，将邻居 B 压入栈：

   • 栈：s = [B, B]

4. 从栈中弹出顶点 B，访问 B：visited = {A, D, E, B}，将邻居 C 压入栈：

   • 栈：s = [B, C]

5. 从栈中弹出顶点 C，访问 C：visited = {A, D, E, B, C}。

   • 栈：s = [B]

6. 从栈中弹出顶点 B，发现已访问，跳过。

7. 栈为空，遍历结束。

最终结果：A -> D -> E -> B -> C

---

深度优先遍历的时间和空间复杂度

1. 时间复杂度：

   • 邻接表表示：$O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。
     • 每个顶点最多被访问一次。
     • 每条边最多被遍历一次。
   • 邻接矩阵表示：$O(V^2)$，因为需要检查矩阵中的每一项。

2. 空间复杂度：

   • 栈或递归调用的深度为 $O(V)$。

---

应用**

1. 连通性检测：
   • 判断无向图是否连通，或找到所有连通分量。
2. 检测环：
   • 深度优先遍历可以检测图中是否存在环。
3. 拓扑排序：
   • 用于有向无环图（DAG）的拓扑排序。
4. 路径搜索：
   • 找到从起点到终点的所有路径。

---