请用C++写一个基于邻接矩阵的广度优先遍历
时间: 2024-05-09 09:15:22 浏览: 12
以下是基于邻接矩阵的广度优先遍历的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 存储顶点的数组
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储邻接矩阵的二维数组
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
typedef struct {
int data[MAX_VERTEX_NUM]; // 存储队列元素的数组
int front; // 队头指针
int rear; // 队尾指针
} Queue;
// 初始化队列
void InitQueue(Queue *Q) {
Q->front = Q->rear = 0;
}
// 判断队列是否为空
int IsEmpty(Queue *Q) {
return Q->front == Q->rear;
}
// 入队
void EnQueue(Queue *Q, int data) {
Q->data[Q->rear++] = data;
}
// 出队
int DeQueue(Queue *Q) {
return Q->data[Q->front++];
}
// 创建邻接矩阵图
void CreateGraph(Graph *G) {
printf("请输入图的顶点数和边数:");
scanf("%d %d", &G->vertex_num, &G->edge_num);
printf("请输入图的顶点信息:");
for (int i = 0; i < G->vertex_num; i++) {
scanf("%d", &G->vertex[i]);
}
// 初始化邻接矩阵
for (int i = 0; i < G->vertex_num; i++) {
for (int j = 0; j < G->vertex_num; j++) {
G->arc[i][j] = 0;
}
}
// 构建邻接矩阵
printf("请输入图的边信息:\n");
for (int k = 0; k < G->edge_num; k++) {
int i, j;
printf("请输入第%d条边的两个顶点序号:", k + 1);
scanf("%d %d", &i, &j);
G->arc[i][j] = 1;
G->arc[j][i] = 1;
}
}
// 广度优先遍历
void BFS(Graph *G, int v) {
Queue Q;
int visited[MAX_VERTEX_NUM] = {0}; // 标记数组,用于记录每个顶点是否被访问过
InitQueue(&Q); // 初始化队列
visited[v] = 1; // 标记v已经被访问
printf("%d ", G->vertex[v]); // 输出v的值
EnQueue(&Q, v); // 将v入队
while (!IsEmpty(&Q)) {
int u = DeQueue(&Q); // 出队
for (int w = 0; w < G->vertex_num; w++) {
if (G->arc[u][w] && !visited[w]) { // 若u和w之间有边且w未被访问过
visited[w] = 1; // 标记w已经被访问
printf("%d ", G->vertex[w]); // 输出w的值
EnQueue(&Q, w); // 将w入队
}
}
}
}
int main() {
Graph G;
CreateGraph(&G);
printf("广度优先遍历结果为:\n");
BFS(&G, 0);
printf("\n");
return 0;
}
```
以上就是基于邻接矩阵的广度优先遍历的C语言实现。