基于C++实现图的深度优先遍历算法,广度优先遍历算法,其中邻接表的创建相当于创建多个单链表
时间: 2024-03-24 17:38:43 浏览: 62
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
好的,我可以回答你的问题。
首先,邻接表是一种存储图的数据结构,它由多个单链表组合而成,每个单链表表示一个顶点的邻接点集合。
图的深度优先遍历算法(DFS)基于递归实现,具体步骤如下:
1. 首先访问起始点,并将其标记为已访问。
2. 遍历起始点的邻接点,对于未访问的邻接点,递归调用 DFS 函数。
3. 重复步骤 2,直到所有可达点都被访问过。
C++代码实现如下:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
vector<int> adj[MAXN]; // 邻接表
bool vis[MAXN]; // 标记数组,标记每个顶点是否被访问过
// DFS 函数
void dfs(int u) {
vis[u] = true; // 标记为已访问
cout << u << " "; // 输出当前访问的顶点
for (int v : adj[u]) {
if (!vis[v]) { // 如果邻接点未被访问,则递归调用 DFS 函数
dfs(v);
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入顶点数和边数
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v; // 输入一条边的两个端点
adj[u].push_back(v); // 添加邻接点
adj[v].push_back(u);
}
dfs(1); // 从起始点 1 开始进行 DFS 遍历
return 0;
}
```
图的广度优先遍历算法(BFS)基于队列实现,具体步骤如下:
1. 首先访问起始点,并将其加入队列。
2. 从队列中取出一个顶点,遍历它的邻接点,并将未访问过的邻接点加入队列。对于已经访问过的顶点,不再加入队列。
3. 重复步骤 2,直到队列为空。
C++代码实现如下:
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 100;
vector<int> adj[MAXN]; // 邻接表
bool vis[MAXN]; // 标记数组,标记每个顶点是否被访问过
// BFS 函数
void bfs(int s) {
queue<int> q; // 队列
q.push(s); // 将起始点加入队列
vis[s] = true; // 标记为已访问
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " "; // 输出当前访问的顶点
for (int v : adj[u]) {
if (!vis[v]) { // 如果邻接点未被访问,则加入队列并标记为已访问
vis[v] = true;
q.push(v);
}
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入顶点数和边数
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v; // 输入一条边的两个端点
adj[u].push_back(v); // 添加邻接点
adj[v].push_back(u);
}
bfs(1); // 从起始点 1 开始进行 BFS 遍历
return 0;
}
```
阅读全文