使用c++中的queue库函数实现邻接矩阵的广度优先遍历
时间: 2024-05-01 11:21:40 浏览: 20
首先,需要定义一个邻接矩阵并存储图。假设邻接矩阵为 $adjMatrix$,图中有 $n$ 个节点,其中 $adjMatrix[i][j]$ 表示节点 $i$ 到节点 $j$ 是否有边相连,若相连则为 $1$,否则为 $0$。
接下来,我们定义一个队列 $q$ 用于存储遍历时的节点,以及一个数组 $visited$ 用于记录每个节点是否被访问过。
具体的广度优先遍历算法实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <queue.h>
#define MAX_NODES 100 // 最大节点数
#define INF 0x7fffffff // 无穷大
int adjMatrix[MAX_NODES][MAX_NODES]; // 邻接矩阵
bool visited[MAX_NODES]; // 访问标记
void bfs(int start, int n)
{
queue q; // 定义队列
for (int i = 0; i < n; i++)
{
visited[i] = false; // 初始化访问标记
}
visited[start] = true; // 标记起始节点已访问
enqueue(&q, start); // 起始节点入队
while (!is_empty(&q))
{
int current = dequeue(&q); // 取出队首节点
printf("%d ", current); // 输出当前节点
// 遍历当前节点的所有邻居
for (int i = 0; i < n; i++)
{
if (adjMatrix[current][i] != 0 && !visited[i])
{
visited[i] = true; // 标记邻居已访问
enqueue(&q, i); // 邻居入队
}
}
}
}
int main()
{
int n = 6; // 节点数
int start = 0; // 起始节点
// 初始化邻接矩阵
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
adjMatrix[i][j] = INF;
}
}
adjMatrix[0][1] = adjMatrix[1][0] = 1;
adjMatrix[0][2] = adjMatrix[2][0] = 1;
adjMatrix[1][2] = adjMatrix[2][1] = 1;
adjMatrix[1][3] = adjMatrix[3][1] = 1;
adjMatrix[2][4] = adjMatrix[4][2] = 1;
adjMatrix[3][4] = adjMatrix[4][3] = 1;
adjMatrix[3][5] = adjMatrix[5][3] = 1;
adjMatrix[4][5] = adjMatrix[5][4] = 1;
bfs(start, n); // 广度优先遍历
return 0;
}
```
上述代码中,我们以一个简单的无向图为例进行了广度优先遍历。其中,我们使用了 C 语言中的 `queue` 库函数实现队列的基本操作,包括队列的创建、入队、出队、判断队列是否为空等操作。
在遍历过程中,我们首先将起始节点入队并标记为已访问,然后进入循环,每次取出队首节点并输出,再遍历当前节点的所有邻居,将未访问过的邻居入队并标记为已访问。直到队列为空,遍历结束。