图的深度优先搜索和广度优先搜索(C++实现)
图的存储方法主要包括邻接矩阵、邻接表、边集数组、邻接多重表等,遍历图的方法有 2 种,分别是深度优先搜索和广度优先搜索。
具体步骤如下:
深度优先搜索的特点如下:
深度优先搜索适用于解决一些问题,如寻找路径、检查图的连通性等。
以下代码实现了一个基于邻接表的深度优先搜索算法,用于遍历无向图:
具体步骤如下:
广度优先搜索的特点如下:
广度优先搜索适用于解决一些问题,如寻找最短路径、检查图的连通性等。
以下代码实现了一个基于邻接表的广度优先搜索算法,用于遍历无向图:
在 bfs() 函数中,使用一个队列 q 来存储待访问的顶点。首先,将起始顶点 start 标记为已访问并将它加入队列。然后进入一个循环,当队列不为空时,取出队首元素 u 并处理(输出)。接着,遍历与 u 相邻的所有顶点 v,如果 v 未被访问过,则将其标记为已访问并加入队列。
深度优先搜索
深度优先搜索(DFS)从图的某个顶点开始,沿着一条路径直到不能继续为止,然后返回并尝试探索其他的路径。直观地感受一下此搜索:我们尽可能深地探索每个可能的路径,直到找到解决方案或确定没有解决方案。具体步骤如下:
- 从起始顶点开始,将其标记为已访问;
- 选择一个未被访问的邻接顶点,将其标记为已访问,并递归地对它进行深度优先搜索;
- 重复,直到无法继续前进,然后回退到上一个顶点,继续探索未访问的顶点。
深度优先搜索的特点如下:
- 使用递归或栈来实现;
- 深度优先搜索会尽可能深地搜索当前路径上的顶点,直到无法继续为止,然后回退。
深度优先搜索适用于解决一些问题,如寻找路径、检查图的连通性等。
以下代码实现了一个基于邻接表的深度优先搜索算法,用于遍历无向图:
#include <iostream> #include <vector> using namespace std; const int MAXN = 105; // 最大顶点数 vector<int> adjList[MAXN]; // 邻接表 bool visited[MAXN]; // 访问标记 int n, m; // n:顶点数,m:边数 void dfs(int u) { visited[u] = true; // 标记顶点 u 为已访问 cout << u << " "; // 处理顶点 u for (int v : adjList[u]) { // 遍历邻接顶点 if (!visited[v]) { dfs(v); // 递归访问相邻的未被访问的顶点 } } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adjList[u].push_back(v); // 对于无向图 adjList[v].push_back(u); // 对于无向图 } cout << "DFS遍历结果:"; dfs(1); // 从顶点 1 开始 DFS cout << endl; return 0; }代码说明:
- 定义了一个常量 MAXN 表示最大顶点数,并创建了一个邻接表 adjList 来存储图中的边信息。
- 访问标记数组 visited 记录每个顶点是否被访问过。接着定义了两个整数变量 n 和 m 分别表示顶点数和边数。
- 函数 dfs() 首先将当前顶点 u 标记为已访问,并输出该顶点。然后遍历与顶点 u 相邻的所有顶点 v,如果 v 未被访问过,则递归调用 dfs() 函数继续遍历。
广度优先搜索
广度优先搜索(BFS)从图的某个顶点开始,先访问其所有的邻接顶点,然后逐层访问下去。广度优先搜索就像是一波波水从起始顶点向外扩散,直到把终止顶点找到为止。具体步骤如下:
- 从起始顶点开始,将其标记为已访问,并将其加入队列;
-
重复以下步骤直到队列为空:
- 出队列一个顶点,访问它;
- 将所有未被访问的邻接顶点加入队列,并标记为已访问。
广度优先搜索的特点如下:
- 使用队列来实现;
- 广度优先搜索会先访问起始顶点的所有邻接顶点,然后逐层访问下去。
广度优先搜索适用于解决一些问题,如寻找最短路径、检查图的连通性等。
以下代码实现了一个基于邻接表的广度优先搜索算法,用于遍历无向图:
#include <iostream> #include <vector> #include <queue> using namespace std; const int MAXN = 105; // 最大顶点数 vector<int> adjList[MAXN]; // 邻接表 bool visited[MAXN]; // 访问标记 int n, m; // n:顶点数,m:边数 void bfs(int start) { queue<int> q; visited[start] = true; // 标记起点已访问 q.push(start); // 起点入队 while (!q.empty()) { // 当队列不为空时循环 int u = q.front(); // 取出队首顶点 q.pop(); cout << u << " "; // 处理顶点 u for (int v : adjList[u]) { // 遍历邻接顶点 if (!visited[v]) { // 若未访问 visited[v] = true; // 标记为已访问 q.push(v); // 将未被访问的相邻顶点加入队列 } } } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { // 读入 m 条边 int u, v; cin >> u >> v; adjList[u].push_back(v); // 对于无向图 adjList[v].push_back(u); // 对于无向图 } cout << "BFS遍历结果:"; bfs(1); // 从顶点 1 开始 BFS cout << endl; return 0; }首先定义了一个常量 MAXN,表示最大顶点数;然后创建了一个邻接表 adjList 来存储图中的边信息,并定义一个访问标记数组 visited 来记录每个顶点是否被访问过。接着,定义了两个整数变量 n 和 m,分别表示顶点数和边数。
在 bfs() 函数中,使用一个队列 q 来存储待访问的顶点。首先,将起始顶点 start 标记为已访问并将它加入队列。然后进入一个循环,当队列不为空时,取出队首元素 u 并处理(输出)。接着,遍历与 u 相邻的所有顶点 v,如果 v 未被访问过,则将其标记为已访问并加入队列。