用c语言实现宽度优先搜索
时间: 2023-10-24 11:04:46 浏览: 38
宽度优先搜索(BFS)是一种图形搜索算法,它从根节点开始,逐层扩展图像,直到找到目标节点。下面是使用C语言实现BFS的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
#define MAX_QUEUE_SIZE 100
typedef struct {
int vertex[MAX_VERTEX_NUM];
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vertex_num;
int edge_num;
} Graph;
int visited[MAX_VERTEX_NUM] = {0}; // 记录节点是否被访问过
void InitGraph(Graph *G) {
int i, j;
printf("请输入节点数和边数:\n");
scanf("%d%d", &G->vertex_num, &G->edge_num);
printf("请输入节点信息:\n");
for (i = 0; i < G->vertex_num; i++) {
scanf("%d", &G->vertex[i]);
}
// 初始化邻接矩阵
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
G->matrix[i][j] = 0;
}
}
// 构建邻接矩阵
printf("请输入边信息(格式为:起点 终点):\n");
for (i = 0; i < G->edge_num; i++) {
int start, end;
scanf("%d%d", &start, &end);
G->matrix[start][end] = 1;
G->matrix[end][start] = 1;
}
}
void BFS(Graph *G, int start) {
int i, j;
int queue[MAX_QUEUE_SIZE];
int front = 0, rear = 0;
printf("BFS:");
printf("%d ", G->vertex[start]);
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int cur = queue[front++];
for (i = 0; i < G->vertex_num; i++) {
if (G->matrix[cur][i] == 1 && visited[i] == 0) {
printf("%d ", G->vertex[i]);
visited[i] = 1;
queue[rear++] = i;
}
}
}
printf("\n");
}
int main() {
Graph G;
int start;
InitGraph(&G);
printf("请输入起始节点:\n");
scanf("%d", &start);
BFS(&G, start);
return 0;
}
```
在上面的代码中,我们使用邻接矩阵来表示图,并使用广度优先搜索来遍历整个图。其中,visited数组用于记录节点是否被访问过,queue数组用于实现队列。首先将起始节点放入队列中,然后依次出队并访问其邻接节点,将其加入队列中,直到队列为空为止。
相关推荐
![](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)