目录😋
任务描述
本关任务：实现图的遍历
相关知识
为了完成本关任务，你需要掌握：
- 深度优先遍历
- 广度优先遍历
一、深度优先遍历
1. 定义
- 深度优先遍历（Depth - First Search，简称 DFS）是一种用于遍历或搜索图（包括树，树是一种特殊的图）的算法。采用递归算法的深度优先遍历是指在遍历图的过程中，通过递归调用函数自身来实现对图中节点的深度优先访问。
- 其基本思想是从给定的起始节点开始，沿着一条路径尽可能深地探索图，直到无法继续或者达到目标节点，然后回溯到前一个节点，继续探索其他未访问的分支路径。
2. 工作原理
（1）初始状态
- 选择一个起始节点，将其标记为已访问，以避免重复访问。
- 通常会使用一个数据结构（如数组、布尔向量等）来记录节点是否被访问过。
（2）递归探索
- 对于起始节点的每一个未访问的邻接节点，递归地调用深度优先遍历函数。这意味着每次找到一个新的邻接节点，就将其视为新的起始节点，继续深入探索它的邻接节点。
- 例如，在一个简单的图中，如果从节点 A 开始，A 有邻接节点 B 和 C。先访问 B，然后对于 B 的未访问邻接节点（假设为 D 和 E），又会分别以 D 和 E 为新的起点进行递归探索，直到所有从 B 可达的节点都被访问，然后回溯到 A，再去访问 C 及其可达节点。
（3）回溯机制
- 当一个节点的所有邻接节点都被访问后，递归函数会返回上一层调用，这就是回溯过程。回溯到上一层后，继续探索上一层节点的其他未访问邻接节点。
- 例如，在上述例子中，当完成对以 B 为起点的所有可达节点的访问后，就会回溯到 A，然后开始访问 C 及其可达节点。
3. 示例代码（以简单图的邻接表表示为例）
以下是一个简单的 C++ 代码示例，用于对一个图进行深度优先遍历：
using namespace std; class Graph { private: int V; vector<vector<int>> adj; public: Graph(int V) { this->V = V; adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); } void DFS(int v, vector<bool>& visited) { visited[v] = true; cout << v << " "; for (int i : adj[v]) { if (!visited[i]) { DFS(i, visited); } } } }; int main() { int V = 5; Graph g(V); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4); vector<bool> visited(V, false); g.DFS(0, visited); return 0; }
在这个示例中：
Graph类表示图，V是顶点数量，adj是邻接表，用于存储每个顶点的邻接顶点。addEdge函数用于向图中添加边，将一个顶点的邻接顶点添加到其对应的邻接表中。DFS函数实现了深度优先遍历。它接受一个顶点索引v和一个用于记录访问状态的向量visited。首先将当前顶点标记为已访问，然后输出当前顶点，接着遍历当前顶点的所有邻接顶点。对于未访问的邻接顶点，递归调用DFS函数进行深度优先遍历。- 在
main函数中，创建了一个有 5 个顶点的图，添加了一些边，初始化了访问向量，然后从顶点 0 开始进行深度优先遍历。4. 优势和应用场景
（1）优势
- 代码简洁直观：对于熟悉递归思想的开发者来说，递归实现的深度优先遍历代码结构相对简单，易于理解和实现。
- 自然地反映深度优先的思想：递归调用的过程很好地模拟了不断深入图的过程，符合深度优先遍历的逻辑。
（2）应用场景
- 图的连通性判断：可以判断一个图是否是连通图，或者找出图中的连通分量。
- 拓扑排序（对于有向无环图）：在对有向无环图进行拓扑排序时，深度优先遍历是一种常用的基础算法。
- 寻找路径：用于在图中寻找从一个节点到另一个节点的路径，如在迷宫求解等问题中，将迷宫看作一个图，使用深度优先遍历寻找从起点到终点的路径。
二、广度优先遍历
1. 定义
- 广度优先遍历（Breadth - First Search，简称 BFS）是一种图的遍历算法。它从给定的起始顶点开始，按照与起始顶点的距离远近，一层一层地向外扩展遍历图中的顶点，直到图中的所有顶点都被访问。在遍历过程中，先访问距离起始顶点距离为 1 的顶点，再访问距离为 2 的顶点，以此类推。
2. 工作原理
（1）初始化
- 首先，将起始顶点标记为已访问，并且将其放入一个队列（Queue）中。队列是一种先进先出（FIFO）的数据结构，这保证了在遍历过程中先访问先加入的顶点的邻接顶点。
（2）迭代过程
- 当队列不为空时，取出队首顶点，访问该顶点，然后遍历这个顶点的所有邻接顶点。对于每个未被访问的邻接顶点，将其标记为已访问，并放入队列中。
- 这样，每次从队列中取出的顶点都是按照距离起始顶点的层次顺序进行的，先处理离起始顶点近的顶点，再逐渐处理更远的顶点。
- 例如，在一个简单的图中，从顶点 A 开始进行广度优先遍历。A 被放入队列，然后取出 A，访问 A 并将 A 的邻接顶点 B、C 放入队列；接着取出 B，访问 B 并将 B 的邻接顶点 D、E 放入队列（如果 D、E 未被访问），以此类推，直到队列为空。
3. 示例代码（以简单图的邻接表表示为例）
以下是一个简单的 C++ 代码示例，用于对一个图进行广度优先遍历：
using namespace std; class Graph { private: int V; vector<vector<int>> adj; public: Graph(int V) { this->V = V; adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); } void BFS(int start) { vector<bool> visited(V, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int v = q.front(); q.pop(); cout << v << " "; for (int i : adj[v]) { if (!visited[i]) { visited[i] = true; q.push(i); } } } } }; int main() { int V = 6; Graph g(V); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(2, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.BFS(0); return 0; }
在这个示例中：
Graph类表示图，V是顶点数量，adj是邻接表，用于存储每个顶点的邻接顶点。addEdge函数用于向图中添加边，将一个顶点的邻接顶点添加到其对应的邻接表中。BFS函数实现了广度优先遍历。它接受一个起始顶点索引start。首先创建一个用于记录访问状态的向量visited和一个队列q，将起始顶点标记为已访问并放入队列。在循环中，只要队列不为空，就取出队首顶点，访问该顶点，然后遍历它的邻接顶点。对于未被访问的邻接顶点，标记为已访问并放入队列。- 在
main函数中，创建了一个有 6 个顶点的图，添加了一些边，然后从顶点 0 开始进行广度优先遍历。4. 优势和应用场景
（1）优势
- 找到最短路径：在无权图（边没有权重的图）中，广度优先遍历可以找到从起始顶点到其他顶点的最短路径长度。因为它是按照距离层次进行遍历的，第一次访问到某个顶点时的路径长度就是最短路径长度。
- 均匀地搜索图：相比于深度优先遍历可能会沿着一条路径深入而忽略其他部分，广度优先遍历可以比较均匀地搜索图，对图的整体结构有更好的探索效果。
（2）应用场景
- 最短路径问题（无权图）：如在社交网络中寻找两个人之间的最短关系链，或者在迷宫中寻找从起点到终点的最短路径（将迷宫看作一个图）。
- 网络爬虫：广度优先遍历可以用于网络爬虫中，从一个起始网页开始，一层一层地爬取链接页面，先爬取离起始网页近的链接，再逐渐向外扩展。
- 连通分量计算：和深度优先遍历一样，也可以用于计算图的连通分量，不过广度优先遍历是按照层次来划分的。
三、带权有向图
带权有向图如下图所示，要求指定初始点，从初始点出发进行图的遍历。
测试说明
平台会对你编写的代码进行测试：
测试输入：
0
预期输出：
从顶点0开始的DFS: 0 1 2 5 4 3 从顶点0开始的BFS: 0 1 3 2 5 4
【提示：输出遍历顶点的格式为 printf("%3d",v);】
开始你的任务吧，祝你成功！
通关代码
// 用于sort using namespace std; class Graph { private: int V; // 顶点数 vector<vector<int>> adj; // 邻接表 public: // 构造函数 Graph(int V) { this->V = V; adj.resize(V); } // 添加有向边 void addEdge(int u, int v) { adj[u].push_back(v); } // 深度优先遍历 void DFS(int start) { vector<bool> visited(V, false); // 访问标记 stack<int> s; // 使用栈实现DFS s.push(start); cout << "从顶点" << start << "开始的DFS:\n"; while (!s.empty()) { int v = s.top(); s.pop(); if (!visited[v]) { visited[v] = true; printf("%3d", v); // 输出顶点 } // 遍历邻接节点，逆序入栈 for (int i = adj[v].size() - 1; i >= 0; --i) { int neighbor = adj[v][i]; if (!visited[neighbor]) { s.push(neighbor); } } } cout << endl; } // 广度优先遍历 void BFS(int start) { vector<bool> visited(V, false); // 访问标记 queue<int> q; // 使用队列实现BFS q.push(start); visited[start] = true; cout << "从顶点" << start << "开始的BFS:\n"; while (!q.empty()) { int v = q.front(); q.pop(); printf("%3d", v); // 输出顶点 // 遍历邻接节点 for (int neighbor : adj[v]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } cout << endl; } // 函数：排序邻接表 void sortAdjacencyList() { for (int i = 0; i < V; ++i) { sort(adj[i].begin(), adj[i].end()); // 对每个邻接链表进行排序 } } }; int main() { int V = 6; // 顶点数量 Graph g(V); // 添加边 (u, v) g.addEdge(5, 4); g.addEdge(4, 3); g.addEdge(3, 2); g.addEdge(2, 0); g.addEdge(0, 1); g.addEdge(0, 3); g.addEdge(1, 2); g.addEdge(3, 5); g.addEdge(2, 5); g.addEdge(5, 0); // 手动控制邻接表的顺序 g.sortAdjacencyList(); int startVertex; cin >> startVertex; // 进行深度优先遍历和广度优先遍历 g.DFS(startVertex); g.BFS(startVertex); return 0; }
测试结果
