用c语言写一个广度优先搜索
时间: 2024-05-09 15:17:28 浏览: 15
好的,我可以帮您解答这个问题。广度优先搜索是一种图的遍历算法,具体实现可以通过队列来实现。以下是用 C 语言实现广度优先搜索的一种简单代码:
```
#include<stdio.h>
#define MAXSIZE 100
int visited[MAXSIZE]; // 定义已访问数组,用于记录节点是否被访问过
int queue[MAXSIZE]; // 定义队列,用于存储待遍历节点
int front = 0, rear = 0; // 定义队列的头尾指针
typedef struct node{ // 定义节点结构体
int data;
struct node *next;
}Node;
void BFS(Node *graph[], int start) // BFS函数
{
visited[start] = 1;
queue[rear++] = start;
while(front < rear) {
int cur = queue[front++]; // 取出队首元素
printf("%d ", cur); // 输出当前节点
Node *temp = graph[cur]->next;
while(temp) { // 遍历当前节点的所有邻接点
if(!visited[temp->data]) { // 如果邻接点未被访问过,加入队列
visited[temp->data] = 1;
queue[rear++] = temp->data;
}
temp = temp->next;
}
}
}
int main()
{
int n, m, start; // n为节点数,m为边数,start为起始节点
scanf("%d %d %d", &n, &m, &start);
Node *graph[n+1]; // 构造邻接表(下标从1开始)
for(int i = 1; i <= n; i++) {
graph[i] = (Node*)malloc(sizeof(Node));
graph[i]->next = NULL;
}
for(int i = 1; i <= m; i++) { // 读入边信息,建立邻接表
int u, v;
scanf("%d %d", &u, &v);
Node *temp1 = (Node*)malloc(sizeof(Node));
temp1->data = v;
temp1->next = graph[u]->next;
graph[u]->next = temp1;
Node *temp2 = (Node*)malloc(sizeof(Node));
temp2->data = u;
temp2->next = graph[v]->next;
graph[v]->next = temp2;
}
BFS(graph, start); // 调用BFS函数遍历图
return 0;
}
```
以上是一种使用邻接表和队列实现的广度优先搜索算法,希望对您有所帮助。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)