广度优先搜索代码c语言
时间: 2024-06-13 17:01:21 浏览: 18
广度优先搜索是一种图搜索算法,用于遍历或搜索树或图的数据结构。它从根节点开始遍历图,逐层扩展下去,直到找到目标节点或遍历完整个图。下面是一个C语言实现广度优先搜索的代码示例:
```
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100 // 最大顶点数
#define MAXQUEUE 100 // 队列长度
typedef struct{
int vexs[MAXVEX]; // 顶点表
int arcs[MAXVEX][MAXVEX]; // 邻接矩阵,可看做边表
int numVertexes, numEdges; // 图中当前的顶点数和边数
}MGraph;
typedef struct{
int data[MAXQUEUE];
int front, rear;
}Queue;
void CreateMGraph(MGraph *G){
// 创建邻接矩阵图
}
void BFS(MGraph G, int start){
int i, j;
int visited[MAXVEX] = {0}; // 记录每个顶点是否被访问过
Queue Q;
Q.front = Q.rear = 0;
printf("%d ", start);
visited[start] = 1;
Q.data[Q.rear++] = start;
while(Q.front != Q.rear){
int k = Q.data[Q.front++];
for(j = 0; j < G.numVertexes; j++){
if(G.arcs[k][j] == 1 && !visited[j]){
printf("%d ", j);
visited[j] = 1;
Q.data[Q.rear++] = j;
}
}
}
}
int main(){
MGraph G;
CreateMGraph(&G);
BFS(G, 0);
return 0;
}
```
这个代码使用了邻接矩阵来存储图,使用队列来实现BFS的过程。在代码中,CreateMGraph()函数是用来创建邻接矩阵图的,BFS()函数是用来实现广度优先搜索的。其中,visited数组是用来记录每个顶点是否被访问过的,Queue结构体则是用来实现队列的,front和rear分别表示队头和队尾的位置。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)