建立无向图的邻接矩阵存储,进行深度优先遍历和广度优先遍历c++
时间: 2023-12-03 07:54:47 浏览: 146
以下是使用邻接矩阵存储的无向图的深度优先遍历和广度优先遍历的C++代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大顶点数
int graph[MAXN][MAXN]; // 邻接矩阵存储
bool visited[MAXN]; // 标记是否已经访问过
// 深度优先遍历
void dfs(int u) {
visited[u] = true;
cout << u << " ";
for (int v = 0; v < MAXN; v++) {
if (graph[u][v] && !visited[v]) {
dfs(v);
}
}
}
// 广度优先遍历
void bfs(int u) {
queue<int> q;
visited[u] = true;
q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int v = 0; v < MAXN; v++) {
if (graph[u][v] && !visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
int main() {
// 初始化邻接矩阵和visited数组
for (int i = 0; i < MAXN; i++) {
visited[i] = false;
for (int j = 0; j < MAXN; j++) {
graph[i][j] = 0;
}
}
// 读入无向图
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u][v] = graph[v][u] = 1;
}
// 深度优先遍历
cout << "DFS: ";
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
}
}
cout << endl;
// 广度优先遍历
for (int i = 0; i < MAXN; i++) {
visited[i] = false;
}
cout << "BFS: ";
for (int i = 0; i < n; i++) {
if (!visited[i]) {
bfs(i);
}
}
cout << endl;
return 0;
}
```
其中,`dfs(int u)` 函数实现了从顶点 `u` 开始的深度优先遍历,`bfs(int u)` 函数实现了从顶点 `u` 开始的广度优先遍历。在遍历时,需要使用 `visited` 数组来标记每个顶点是否已经访问过,避免重复访问。
阅读全文