C++完成图的深度优先遍历算法、广度优先遍历算法。其中,邻接表的 创建相当于创建多个单链表。
时间: 2024-03-17 10:46:26 浏览: 63
利用邻接表实现图的深度优先遍历
好的,对于你的问题,我可以回答如下:
首先,图的深度优先遍历算法和广度优先遍历算法是两种不同的图遍历方式。深度优先遍历算法(Depth First Search,DFS)是一种先探索某一节点的所有分支,再逐级回溯的遍历方式。广度优先遍历算法(Breadth First Search,BFS)则是一种层次遍历方式,即先遍历距离起始节点最近的节点。
对于邻接表的创建,你所说的是正确的,邻接表的创建可以看作是创建多个单链表。邻接表是一种图的存储结构,采用链式存储方式,对于每个节点,都存储了与之相邻的节点信息,以及连接这些节点的边的信息。
下面是C++实现图的深度优先遍历算法和广度优先遍历算法的示例代码(假设图是无向图):
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大节点数
int head[MAXN], vis[MAXN]; // head数组存储每个节点的第一个邻接点,vis数组用于标记已访问的节点
struct Edge { // 存储边的信息
int to, next;
} edge[MAXN * 2]; // 因为是无向图,所以边的数量是节点数的两倍
int cnt = 0; // 记录边的数量
void addEdge(int u, int v) { // 添加边的信息
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
void dfs(int u) { // 深度优先遍历
vis[u] = 1;
cout << u << " "; // 遍历到节点u,输出节点u的编号
for (int i = head[u]; i; i = edge[i].next) { // 遍历节点u的邻接点
int v = edge[i].to;
if (!vis[v]) dfs(v); // 如果该邻接点还未访问过,则继续遍历
}
}
void bfs(int u) { // 广度优先遍历
queue<int> q;
q.push(u);
vis[u] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
cout << x << " "; // 遍历到节点x,输出节点x的编号
for (int i = head[x]; i; i = edge[i].next) { // 遍历节点x的邻接点
int v = edge[i].to;
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
}
int main() {
int n, m; // n为节点数,m为边数
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v); // 添加边的信息
addEdge(v, u); // 因为是无向图,所以需要反向再添加一次
}
dfs(1); // 从节点1开始深度优先遍历
cout << endl;
memset(vis, 0, sizeof(vis)); // 将vis数组清零
bfs(1); // 从节点1开始广度优先遍历
cout << endl;
return 0;
}
```
希望我的回答对你有所帮助!
阅读全文