87 lines
2.2 KiB
C
87 lines
2.2 KiB
C
|
#include <stdio.h>
|
||
|
|
#include <stdbool.h>
|
||
|
|
#include <stdlib.h>
|
||
|
|
|
||
|
|
#define MAX_VERTICES 5 // 图的最大顶点数
|
||
|
|
|
||
|
|
// 图的邻接矩阵表示
|
||
|
|
int graph[MAX_VERTICES][MAX_VERTICES] = {
|
||
|
|
{0, 1, 1, 0, 0},
|
||
|
|
{1, 0, 1, 1, 0},
|
||
|
|
{1, 1, 0, 0, 1},
|
||
|
|
{0, 1, 0, 0, 1},
|
||
|
|
{0, 0, 1, 1, 0}
|
||
|
|
};
|
||
|
|
|
||
|
|
bool visited[MAX_VERTICES]; // 访问标记数组，用来记录哪些节点已经被访问过
|
||
|
|
|
||
|
|
// 队列结构
|
||
|
|
typedef struct {
|
||
|
|
int items[MAX_VERTICES]; // 队列的数组表示
|
||
|
|
int front; // 队列的前端
|
||
|
|
int rear; // 队列的尾端
|
||
|
|
} Queue;
|
||
|
|
|
||
|
|
// 队列操作函数
|
||
|
|
|
||
|
|
// 初始化队列
|
||
|
|
void initQueue(Queue *q) {
|
||
|
|
q->front = 0;
|
||
|
|
q->rear = -1; // 队列初始化为空
|
||
|
|
}
|
||
|
|
|
||
|
|
// 检查队列是否为空
|
||
|
|
int isEmpty(Queue *q) {
|
||
|
|
return q->front > q->rear;
|
||
|
|
}
|
||
|
|
|
||
|
|
// 入队操作
|
||
|
|
void enqueue(Queue *q, int value) {
|
||
|
|
if (q->rear < MAX_VERTICES - 1) { // 如果队列未满
|
||
|
|
q->items[++(q->rear)] = value; // 将新元素添加到队列的尾端
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// 出队操作
|
||
|
|
int dequeue(Queue *q) {
|
||
|
|
if (!isEmpty(q)) {
|
||
|
|
return q->items[(q->front)++]; // 从队列的前端取出一个元素
|
||
|
|
}
|
||
|
|
return -1; // 队列为空时返回 -1
|
||
|
|
}
|
||
|
|
|
||
|
|
// 广度优先遍历 BFS 函数
|
||
|
|
void bfs(int start, int n) {
|
||
|
|
Queue q;
|
||
|
|
initQueue(&q); // 初始化队列
|
||
|
|
|
||
|
|
enqueue(&q, start); // 将起始节点入队
|
||
|
|
visited[start] = true; // 标记起始节点已访问
|
||
|
|
|
||
|
|
while (!isEmpty(&q)) { // 队列不为空时，继续遍历
|
||
|
|
int current = dequeue(&q); // 从队列中取出一个节点
|
||
|
|
printf("%d ", current); // 输出当前节点
|
||
|
|
|
||
|
|
// 遍历当前节点的所有邻接节点
|
||
|
|
for (int i = 0; i < n; i++) {
|
||
|
|
if (graph[current][i] == 1 && !visited[i]) { // 如果当前节点和 i 节点之间有边且 i 节点未被访问
|
||
|
|
enqueue(&q, i); // 将 i 节点入队
|
||
|
|
visited[i] = true; // 标记 i 节点已访问
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
int n = MAX_VERTICES; // 图的顶点数
|
||
|
|
for (int i = 0; i < n; i++) {
|
||
|
|
visited[i] = false; // 初始化访问标记数组，将所有节点标记为未访问
|
||
|
|
}
|
||
|
|
|
||
|
|
printf("广度优先遍历（BFS）：\n");
|
||
|
|
bfs(0, n); // 从顶点 0 开始进行 BFS 遍历
|
||
|
|
printf("\n");
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|