用C++代码实现元素类型为整形的图的广度优先遍历算法,写出主函数
时间: 2024-02-09 15:08:51 浏览: 53
以下是使用邻接表实现的图的广度优先遍历算法的C++代码,包括主函数:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 100;
// 邻接表结点
struct Node {
int val; // 结点值
int next; // 指向下一个邻接点的指针
};
// 邻接表
struct Graph {
Node nodes[MAXN]; // 结点数组
int heads[MAXN]; // 头结点数组
int cnt; // 结点数量
Graph() {
cnt = 0;
for (int i = 0; i < MAXN; i++) {
heads[i] = -1;
}
}
// 添加一条边
void addEdge(int u, int v) {
nodes[cnt].val = v;
nodes[cnt].next = heads[u];
heads[u] = cnt++;
}
};
// 广度优先遍历
void bfs(Graph &g, int start) {
queue<int> q;
bool visited[MAXN] = {false};
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int i = g.heads[u]; i != -1; i = g.nodes[i].next) {
int v = g.nodes[i].val;
if (!visited[v]) {
q.push(v);
visited[v] = true;
}
}
}
}
int main() {
Graph g;
int n, m; // n为结点个数,m为边数
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g.addEdge(u, v);
g.addEdge(v, u);
}
bfs(g, 0);
return 0;
}
```
在主函数中,我们首先读入图的结点个数和边数,然后依次读入每一条边并添加到邻接表中。最后调用bfs函数进行广度优先遍历。
阅读全文