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

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

01.图的遍历

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

广度优先

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

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

基本思路

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

---

代码语言：javascript代码运行次数：0运行复制

void BFS(ct 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 (!())
	{
		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);
			}
		}
	}
}

---

详细步骤与例子

假设图如下（无向图）：

代码语言：javascript代码运行次数：0运行复制

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

图的邻接表表示：

代码语言：javascript代码运行次数：0运行复制

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. 递归查剩余的两个盒子

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

代码语言：javascript代码运行次数：0运行复制

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(ct V& src)
{
	size_t srci = GetVertexIndex(src);
	vector<bool> visited(_vertexs.size(), false);
	_DFS(src, visited);
}

---

深度优先遍历的特点

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

---

基本思路

1. 初始化

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

2. 递归实现

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

. 使用显式栈

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

---

非递归实现（使用栈）

代码语言：javascript代码运行次数：0运行复制

void DFS(Graph& graph, ct V& start) {
    stack<V> s;                // 栈用于存储待访问的顶点
    unordered_set<V> visited;  // 标记已访问顶点

    s.push(start);             // 将起始顶点压入栈

    while (!()) {
        V current = ();   // 取出栈顶顶点
        s.pop();

        if (visited.find(current) == ()) {
            // 标记当前顶点为已访问
            visited.insert(current);

            // 处理当前顶点（例如打印）
            cout << current << " ";

            // 将未访问的邻居压入栈
            for (ct auto& neighbor : graph.Geteighbors(current)) {
                if (visited.find(neighbor) == ()) {
                    s.push(neighbor);
                }
            }
        }
    }
}

---

详细过程与示例

假设图如下（无向图）：

代码语言：javascript代码运行次数：0运行复制

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

邻接表表示：

代码语言：javascript代码运行次数：0运行复制

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

---

1. 非递归实现

初始状态：

• 栈：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. 路径搜索：
   • 到从起点到终点的所有路径。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-12-25，如有侵权请联系 cloudcommunity@tencent 删除前往查看遍历递归队列集合c++