C++ 广度优先搜索方式遍历图;
时间: 2023-06-12 08:04:05 浏览: 65
广度优先搜索(BFS)是一种用于图遍历的算法,它从一个源节点开始,逐层遍历图中所有节点,直到找到目标节点或遍历完整张图。
BFS 的遍历方式是从源节点开始,将其加入队列中,然后遍历与其相邻的节点,将这些节点加入队列中,接着从队列中取出一个节点作为下一轮的源节点,重复上述步骤,直到队列为空或者找到目标节点为止。
在实现 BFS 时,需要使用一个队列来存储待遍历的节点。同时,还需要一个数组来记录每个节点是否已经被遍历过。
下面是一个使用 C 语言实现 BFS 遍历图的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大节点数
typedef struct node {
int data;
struct node *next;
} Node;
typedef struct {
Node *first; // 邻接表头指针
} Vertex;
typedef struct {
Vertex vertexes[MAX_VERTEX_NUM]; // 邻接表
int visited[MAX_VERTEX_NUM]; // 记录节点是否已经被遍历过
int vertex_num; // 实际节点数
} Graph;
typedef struct {
int data[MAX_VERTEX_NUM]; // 队列数组
int front, rear; // 队列头部和尾部指针
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = q->rear = -1;
}
// 判断队列是否为空
int isQueueEmpty(Queue *q) {
return q->front == -1;
}
// 入队
void enqueue(Queue *q, int data) {
if (q->front == -1) {
q->front = q->rear = 0;
} else {
q->rear++;
}
q->data[q->rear] = data;
}
// 出队
int dequeue(Queue *q) {
int data = q->data[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front++;
}
return data;
}
// 添加边
void addEdge(Graph *g, int u, int v) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = v;
node->next = g->vertexes[u].first;
g->vertexes[u].first = node;
}
// 初始化图
void initGraph(Graph *g, int n) {
g->vertex_num = n;
for (int i = 0; i < n; i++) {
g->vertexes[i].first = NULL;
g->visited[i] = 0;
}
}
// BFS 遍历
void bfs(Graph *g, int s) {
Queue q;
initQueue(&q);
g->visited[s] = 1;
printf("%d ", s);
enqueue(&q, s);
while (!isQueueEmpty(&q)) {
int u = dequeue(&q);
for (Node *node = g->vertexes[u].first; node != NULL; node = node->next) {
int v = node->data;
if (!g->visited[v]) {
g->visited[v] = 1;
printf("%d ", v);
enqueue(&q, v);
}
}
}
}
int main() {
Graph g;
initGraph(&g, 5);
addEdge(&g, 0, 1);
addEdge(&g, 0, 2);
addEdge(&g, 1, 2);
addEdge(&g, 2, 0);
addEdge(&g, 2, 3);
addEdge(&g, 3, 3);
bfs(&g, 2);
return 0;
}
```
上述代码中,我们通过邻接表来表示图,其中 `vertexes` 数组用于存储每个节点的邻接表,`visited` 数组用于记录每个节点是否已经被遍历过。在 `bfs` 函数中,我们使用队列来存储待遍历的节点,首先将源节点入队,并标记为已访问。然后,我们从队列中取出一个节点,并遍历与其相邻的节点,将未访问过的节点入队,并标记为已访问。重复这个过程,直到队列为空为止。在遍历每个节点时,我们还会输出其数据,以便观察遍历顺序。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)