当前位置：首页 > news >正文

【C++数据结构——图】图的遍历（头歌教学实验平台习题）【合集】

news 2025/1/8 19:43:17

目录😋

任务描述

本关任务：实现图的遍历

相关知识

为了完成本关任务，你需要掌握：

深度优先遍历
广度优先遍历

一、深度优先遍历

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++ 代码示例，用于对一个图进行深度优先遍历：
#include <iostream>
#include <vector>
#include <algorithm>
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++ 代码示例，用于对一个图进行广度优先遍历：
#include <iostream>
#include <vector>
#include <queue>
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);】

开始你的任务吧，祝你成功！

通关代码

#include <iostream>  
#include <vector>  
#include <queue>  
#include <stack>  
#include <algorithm> // 用于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;  
}