广度优先算法 c语言
时间: 2023-11-10 07:04:17 浏览: 58
广度优先算法(BFS)是一种图遍历算法,它从图的某个顶点开始遍历,先访问该顶点,然后依次访问该顶点的邻接点,再访问邻接点的邻接点,直到遍历完整个图。BFS 通常使用队列来实现。
以下是一个使用 C 语言实现 BFS 的示例代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
typedef struct {
int data[MAX_VERTICES];
int front, rear;
} Queue;
void initQueue(Queue *q) {
q->front = q->rear = -1;
}
bool isEmpty(Queue *q) {
return q->front == -1;
}
bool isFull(Queue *q) {
return q->rear == MAX_VERTICES - 1;}
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full.\n");
return;
}
if (isEmpty(q)) {
q->front = q->rear = 0;
} else {
q->rear++;
}
q->data[q->rear] = value;
}
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return -1;
}
int value = q->data[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front++;
}
return value;
}
void bfs(int graph[][MAX_VERTICES], int start, int n) {
Queue q;
initQueue(&q);
bool visited[MAX_VERTICES] = {false};
visited[start] = true;
enqueue(&q, start);
while (!isEmpty(&q)) {
int vertex = dequeue(&q);
printf("%d ", vertex);
for (int i = 0; i < n; i++) {
if (graph[vertex][i] == 1 && !visited[i]) {
visited[i] = true;
enqueue(&q, i);
}
}
}
}
int main() {
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 1, 0},
{0, 1, 1, 0, 1},
{0, 1, 0, 1, 0}
};
bfs(graph, 0, 5);
return 0;
}
```
该代码使用邻接矩阵表示图,其中 `graph[i][j]` 表示顶点 i 和 j 是否相邻。`bfs` 函数使用队列实现 BFS,从 start 开始遍历图,n 表示图中顶点的数量。