广度优先遍历EXAMPLEC语言
时间: 2024-09-30 21:13:26 浏览: 8
广度优先遍历(Breadth-First Search, BFS)是一种用于遍历或搜索树形结构和图的数据结构的算法。在C语言中,你可以使用队列数据结构来实现BFS。下面是一个简单的例子,展示如何使用BFS遍历无向图中的节点:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// 图节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* newNode(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
// 添加边到邻接表
void addEdge(Node** adj, int v, int w) {
Node* node = newNode(w);
node->next = adj[v];
adj[v] = node;
}
// 广度优先遍历
void bfs(Node** adj, int start) {
int visited[MAX] = {0}; // 初始化访问数组
Node* queue = NULL; // 队列头指针
Node* front = NULL; // 队列尾指针
visited[start] = 1; // 标记起点已访问
front = newNode(start); // 将起点入队
while (queue != NULL) {
Node* temp = front;
front = front->next;
// 输出当前节点
printf("%d ", temp->data);
// 将当前节点的所有未访问邻居入队
for (Node* node = adj[temp->data]; node != NULL; node = node->next) {
if (!visited[node->data]) {
visited[node->data] = 1;
queue = newNode(node->data);
queue->next = front;
front = queue;
}
}
}
}
int main() {
Node* adj[MAX][MAX]; // 使用邻接矩阵表示图
int V = 5; // 图的顶点数
int edges[] = {0, 1, 1, 2, 2, 3, 4, 3, 4, 4}; // 边连接信息
// 填充邻接矩阵
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
adj[i][j] = NULL;
for (int i = 0; i < sizeof(edges)/sizeof(edges[0]); i += 2)
addEdge(adj, edges[i], edges[i+1]);
// 开始BFS
printf("BFS traversal from vertex 0: ");
bfs(adj, 0);
return 0;
}
```
在这个例子中,我们使用邻接矩阵表示图,然后从给定的起始节点开始,按层次顺序访问节点。