编写一个c++代码实现以邻接矩阵为图的存储结构的dfs和bfs
时间: 2023-12-03 14:43:16 浏览: 34
以下是使用邻接矩阵为图的存储结构实现DFS和BFS的C++代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100;
int n, m; // n:顶点数,m:边数
int G[MAXN][MAXN]; // 邻接矩阵存储图
bool visited[MAXN]; // 标记每个结点是否被访问过
// 深度优先遍历
void DFS(int u) {
visited[u] = true; // 标记结点u已访问过
cout << u << " "; // 输出结点u
for (int v = 0; v < n; v++) { // 枚举结点u的所有邻居
if (G[u][v] && !visited[v]) { // 如果结点v是结点u的邻居且未被访问过
DFS(v); // 递归访问结点v
}
}
}
// 广度优先遍历
void BFS(int s) {
queue<int> q; // 定义队列q
visited[s] = true; // 标记结点s已访问过
q.push(s); // 将结点s入队
while (!q.empty()) { // 当队列不为空时
int u = q.front(); // 取出队首结点u
q.pop(); // 将结点u出队
cout << u << " "; // 输出结点u
for (int v = 0; v < n; v++) { // 枚举结点u的所有邻居
if (G[u][v] && !visited[v]) { // 如果结点v是结点u的邻居且未被访问过
visited[v] = true; // 标记结点v已访问过
q.push(v); // 将结点v入队
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = 1; // 无向图
}
// DFS遍历
cout << "DFS: ";
for (int u = 0; u < n; u++) {
if (!visited[u]) { // 如果结点u未被访问过
DFS(u); // 从结点u开始进行DFS遍历
}
}
cout << endl;
// BFS遍历
memset(visited, false, sizeof(visited)); // 初始化visited数组
cout << "BFS: ";
for (int u = 0; u < n; u++) {
if (!visited[u]) { // 如果结点u未被访问过
BFS(u); // 从结点u开始进行BFS遍历
}
}
cout << endl;
return 0;
}
```
其中,输入格式为:
```
n m
u1 v1
u2 v2
...
um vm
```
其中n表示结点数,m表示边数,接下来m行表示每条边的两个端点u和v。
输出为DFS遍历和BFS遍历的结果。