pta图的广度优先遍历c语言
时间: 2023-06-23 14:53:14 浏览: 58
下面是使用队列实现的P图的广度优先遍历的C语言代码:
```c
#include <stdio.h>
#define MAX_N 100 // 图中最大的顶点数
int G[MAX_N][MAX_N]; // 图的邻接矩阵
int visited[MAX_N]; // 记录每个顶点是否被访问过的数组
int N; // 图中顶点的总数
void bfs(int s) {
// 初始化visited数组
for (int i = 0; i < N; i++) {
visited[i] = 0;
}
// 创建一个队列
int queue[MAX_N];
int front = 0, rear = 0;
// 将起点s入队
queue[rear++] = s;
visited[s] = 1;
// 开始广度优先遍历
while (front < rear) {
// 取出队首元素
int cur = queue[front++];
// 输出当前顶点的编号
printf("%d ", cur);
// 遍历cur的所有邻接顶点
for (int i = 0; i < N; i++) {
// 如果i是cur的邻接顶点且未被访问过,则将i入队
if (G[cur][i] && !visited[i]) {
queue[rear++] = i;
visited[i] = 1;
}
}
}
}
int main() {
// 读入图的顶点数
scanf("%d", &N);
// 读入图的邻接矩阵
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &G[i][j]);
}
}
// 从顶点0开始进行广度优先遍历
bfs(0);
return 0;
}
```
在该代码中,我们使用了一个数组visited来记录每个顶点是否被访问过,以避免重复访问。我们还使用了一个队列来存储待访问的顶点。在每次取出队首元素后,我们遍历该顶点的所有邻接顶点,并将未被访问过的邻接顶点入队。这样就可以保证所有的顶点都被访问到,并且按照广度优先的顺序进行遍历。