BFS算法

算法描述总结

BFS（广度优先搜索）是一种逐层遍历图的算法，核心逻辑基于队列实现 “先进先出” 的访问顺序：

1. 初始化：访问起点并标记，将起点入队；
2. 循环处理队列：取出队首节点，遍历其所有邻接节点；
3. 邻接节点处理：对未访问的邻接节点，执行 “访问→标记→入队” 操作；
4. 非连通图兼容：通过外层循环遍历所有未访问顶点，确保所有连通分量都被处理。

代码

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20
#define TRUE 1
#define FALSE 0

typedef char VertexType;

typedef struct ArcNode {
    int adjvex;
    struct ArcNode* nextarc;
} ArcNode;

typedef struct VNode {
    VertexType data;
    ArcNode* firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int visited[MAX_VERTEX_NUM];

typedef struct {
    int data[MAX_VERTEX_NUM];
    int front, rear;
} Queue;

void InitQueue(Queue* Q) {
    Q->front = Q->rear = 0;
}

void EnQueue(Queue* Q, int v) {
    Q->data[Q->rear] = v;
    Q->rear = (Q->rear + 1) % MAX_VERTEX_NUM;
}

int DeQueue(Queue* Q) {
    int v = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_VERTEX_NUM;
    return v;
}

int QueueEmpty(Queue Q) {
    return Q.front == Q.rear;
}

void BFS(ALGraph G, int v) {
    Queue Q;
    InitQueue(&Q);
    printf("%c ", G.vertices[v].data);
    visited[v] = TRUE;
    EnQueue(&Q, v);

    while (!QueueEmpty(Q)) {
        v = DeQueue(&Q);
        ArcNode* p = G.vertices[v].firstarc;
        while (p) {
            int w = p->adjvex;
            if (!visited[w]) {
                printf("%c ", G.vertices[w].data);
                visited[w] = TRUE;
                EnQueue(&Q, w);
            }
            p = p->nextarc;
        }
    }
}

void BFSTraverse(ALGraph G) {
    for (int v = 0; v < G.vexnum; v++)
        visited[v] = FALSE;
    for (int v = 0; v < G.vexnum; v++)
        if (!visited[v])
            BFS(G, v);
}

// 新增：打印图的结构（邻接表形式）
void PrintGraph(ALGraph G) {
    printf("\n图的结构（邻接表）：\n");
    for (int i = 0; i < G.vexnum; i++) {
        printf("顶点 %c -> ", G.vertices[i].data);  // 当前顶点
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {  // 遍历所有邻接顶点
            printf("%c ", G.vertices[p->adjvex].data);
            p = p->nextarc;
        }
        printf("\n");
    }
}

int main() {
    ALGraph G;
    G.vexnum = 4;
    G.arcnum = 3;
    G.vertices[0].data = 'A';
    G.vertices[1].data = 'B';
    G.vertices[2].data = 'C';
    G.vertices[3].data = 'D';

    // 构建边（无向图，双向连接）
    ArcNode* ab = (ArcNode*)malloc(sizeof(ArcNode));
    ab->adjvex = 1; ab->nextarc = NULL;
    G.vertices[0].firstarc = ab;

    ArcNode* ac = (ArcNode*)malloc(sizeof(ArcNode));
    ac->adjvex = 2; ac->nextarc = G.vertices[0].firstarc;
    G.vertices[0].firstarc = ac;

    ArcNode* bd = (ArcNode*)malloc(sizeof(ArcNode));
    bd->adjvex = 3; bd->nextarc = NULL;
    G.vertices[1].firstarc = bd;

    ArcNode* ba = (ArcNode*)malloc(sizeof(ArcNode));
    ba->adjvex = 0; ba->nextarc = G.vertices[1].firstarc;
    G.vertices[1].firstarc = ba;

    ArcNode* ca = (ArcNode*)malloc(sizeof(ArcNode));
    ca->adjvex = 0; ca->nextarc = NULL;
    G.vertices[2].firstarc = ca;

    ArcNode* db = (ArcNode*)malloc(sizeof(ArcNode));
    db->adjvex = 1; db->nextarc = NULL;
    G.vertices[3].firstarc = db;

    // 打印图结构
    PrintGraph(G);

    // 执行BFS遍历
    printf("\nBFS遍历结果：");
    BFSTraverse(G);  // 输出：A B C D

    return 0;
}

时间复杂度

对于邻接表存储的图，每个顶点被访问一次（时间复杂度 ​O(V)），每条边被遍历一次（时间复杂度 ​O(E)），因此总时间复杂度为 ​\boxed{O(V+E)}（其中 ​V 为顶点数，​E 为边数）。

空间复杂度

主要开销来自队列和访问标记数组： - 队列最多存储所有顶点（最坏情况如链式结构），空间复杂度 ​O(V)； - 访问标记数组 visited 的空间复杂度为 ​O(V)； 因此总空间复杂度为 ​\boxed{O(V)}。