写一个BFS的c++程序
时间: 2023-05-14 07:06:01 浏览: 57
#include <stdio.h>
#define MAX_NUM 100 int Graph[MAX_NUM][MAX_NUM];
int visited[MAX_NUM];
int N, E; void BFS(int start){
int queue[MAX_NUM], front = 0, rear = 0;
int i, j; // 把起始顶点放入队列
queue[rear] = start;
rear++; // 已经把起始顶点访问了
visited[start] = 1; while (front < rear){
// 取出队首元素
i = queue[front];
front++;
printf("%d ", i); // 把i的所有邻接点加入队列
for (j = 1; j <= N; j++){
if (Graph[i][j] == 1 && visited[j] == 0){
queue[rear] = j;
rear++;
visited[j] = 1;
}
}
}
} int main(){
int i, j, start; printf("请输入顶点数和边数:");
scanf("%d %d", &N, &E); // 读入邻接矩阵
for (i = 1; i <= N; i++){
for (j = 1; j <= N; j++){
Graph[i][j] = 0;
}
} for (i = 1; i <= E; i++){
int n1, n2;
printf("输入边(Vi, Vj)上的顶点序号:");
scanf("%d %d", &n1, &n2);
Graph[n1][n2] = 1;
Graph[n2][n1] = 1;
} printf("输入起始顶点:");
scanf("%d", &start); printf("BFS遍历结果:");
BFS(start);
printf("\n"); return 0;
}