【数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】
【数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】
Rossy Yan
修改于 2024-12-26 10:04:33
修改于 2024-12-26 10:04:33
任务描述
本关任务：编写一个程序实现图的遍历。
相关知识
为了完成本关任务，你需要掌握：
- 深度优先遍历（采用递归算法）
- 广度优先遍历
深度优先遍历
1. 定义
- 深度优先遍历（Depth - First Search，简称 DFS）是一种用于遍历或搜索图（包括树，树是一种特殊的图）的算法。采用递归算法的深度优先遍历是指在遍历图的过程中，通过递归调用函数自身来实现对图中节点的深度优先访问。
- 其基本思想是从给定的起始节点开始，沿着一条路径尽可能深地探索图，直到无法继续或者达到目标节点，然后回溯到前一个节点，继续探索其他未访问的分支路径。
2. 工作原理
初始状态
- 选择一个起始节点，将其标记为已访问，以避免重复访问。
- 通常会使用一个数据结构（如数组、布尔向量等）来记录节点是否被访问过。
递归探索
- 对于起始节点的每一个未访问的邻接节点，递归地调用深度优先遍历函数。这意味着每次找到一个新的邻接节点，就将其视为新的起始节点，继续深入探索它的邻接节点。
- 例如，在一个简单的图中，如果从节点 A 开始，A 有邻接节点 B 和 C。先访问 B，然后对于 B 的未访问邻接节点（假设为 D 和 E），又会分别以 D 和 E 为新的起点进行递归探索，直到所有从 B 可达的节点都被访问，然后回溯到 A，再去访问 C 及其可达节点。
回溯机制
- 当一个节点的所有邻接节点都被访问后，递归函数会返回上一层调用，这就是回溯过程。回溯到上一层后，继续探索上一层节点的其他未访问邻接节点。
- 例如，在上述例子中，当完成对以 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. 定义
- 广度优先遍历（Breadth - First Search，简称 BFS）是一种图的遍历算法。它从给定的起始顶点开始，按照与起始顶点的距离远近，一层一层地向外扩展遍历图中的顶点，直到图中的所有顶点都被访问。在遍历过程中，先访问距离起始顶点距离为 1 的顶点，再访问距离为 2 的顶点，以此类推。
2. 工作原理
初始化
- 首先，将起始顶点标记为已访问，并且将其放入一个队列（Queue）中。队列是一种先进先出（FIFO）的数据结构，这保证了在遍历过程中先访问先加入的顶点的邻接顶点。
迭代过程
- 当队列不为空时，取出队首顶点，访问该顶点，然后遍历这个顶点的所有邻接顶点。对于每个未被访问的邻接顶点，将其标记为已访问，并放入队列中。
- 这样，每次从队列中取出的顶点都是按照距离起始顶点的层次顺序进行的，先处理离起始顶点近的顶点，再逐渐处理更远的顶点。
- 例如，在一个简单的图中，从顶点 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. 优势和应用场景
优势
- 找到最短路径：在无权图（边没有权重的图）中，广度优先遍历可以找到从起始顶点到其他顶点的最短路径长度。因为它是按照距离层次进行遍历的，第一次访问到某个顶点时的路径长度就是最短路径长度。
- 均匀地搜索图：相比于深度优先遍历可能会沿着一条路径深入而忽略其他部分，广度优先遍历可以比较均匀地搜索图，对图的整体结构有更好的探索效果。
应用场景
- 最短路径问题（无权图）：如在社交网络中寻找两个人之间的最短关系链，或者在迷宫中寻找从起点到终点的最短路径（将迷宫看作一个图）。
- 网络爬虫：广度优先遍历可以用于网络爬虫中，从一个起始网页开始，一层一层地爬取链接页面，先爬取离起始网页近的链接，再逐渐向外扩展。
- 连通分量计算：和深度优先遍历一样，也可以用于计算图的连通分量，不过广度优先遍历是按照层次来划分的。
带权有向图 带权有向图如下图所示，要求指定初始点，从初始点出发进行图的遍历。
测试说明
平台会对你编写的代码进行测试：
测试输入：
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;
}测试结果
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-12-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
