c++使用队列完成邻接矩阵的广度优先遍历
时间: 2024-01-12 20:05:41 浏览: 27
下面是使用队列实现邻接矩阵的广度优先遍历的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 存储顶点的数组
int edge[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 init_queue(Queue *q) {
q->front = q->rear = 0;
}
// 判断队列是否为空
int is_empty(Queue *q) {
return q->front == q->rear;
}
// 判断队列是否已满
int is_full(Queue *q) {
return q->rear == MAX_VERTEX_NUM;
}
// 入队
void enqueue(Queue *q, int data) {
if (is_full(q)) {
printf("队列已满\n");
return;
}
q->data[q->rear++] = data;
}
// 出队
int dequeue(Queue *q) {
if (is_empty(q)) {
printf("队列已空\n");
return -1;
}
return q->data[q->front++];
}
// 广度优先遍历
void bfs(Graph *g, int start) {
Queue q;
init_queue(&q);
int visited[MAX_VERTEX_NUM] = {0}; // 记录顶点是否被访问过的数组
// 将起始顶点入队并标记已访问
enqueue(&q, start);
visited[start] = 1;
while (!is_empty(&q)) {
int vertex = dequeue(&q);
printf("%d ", vertex);
// 遍历与当前顶点相邻的未访问过的顶点,并将其入队并标记已访问
for (int i = 0; i < g->vertex_num; i++) {
if (g->edge[vertex][i] == 1 && !visited[i]) {
enqueue(&q, i);
visited[i] = 1;
}
}
}
}
int main() {
Graph g;
g.vertex_num = 5;
g.edge_num = 7;
for (int i = 0; i < g.vertex_num; i++) {
g.vertex[i] = i;
}
// 初始化邻接矩阵
for (int i = 0; i < g.vertex_num; i++) {
for (int j = 0; j < g.vertex_num; j++) {
g.edge[i][j] = 0;
}
}
// 添加边
g.edge[0][1] = 1;
g.edge[0][2] = 1;
g.edge[1][3] = 1;
g.edge[1][4] = 1;
g.edge[2][4] = 1;
g.edge[3][4] = 1;
g.edge[4][3] = 1;
bfs(&g, 0); // 从顶点0开始遍历
return 0;
}
```
在这个例子中,我们定义了一个 `Graph` 结构体来存储邻接矩阵,其中包含一个存储顶点的数组和一个存储邻接矩阵的二维数组。我们还定义了一个 `Queue` 结构体来实现队列,并定义了一些常用的队列操作函数。在 `bfs` 函数中,我们首先将起始顶点入队并标记已访问,然后不断从队列中取出元素进行遍历,并将与当前顶点相邻的未访问过的顶点入队并标记已访问。最后,当队列为空时,遍历结束。