邻接表广度优先算法c语言

邻接表广度优先算法是一种常用的图遍历算法，以下是使用 C 语言实现邻接表广度优先算法的示例代码：

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

#define MAX_VERTEX_NUM 100   // 最大顶点数
#define FALSE 0
#define TRUE 1

typedef int Boolean;
Boolean visited[MAX_VERTEX_NUM];    // 记录已访问的顶点

// 邻接表中的边结点
typedef struct ArcNode {
    int adjvex;                 // 邻接点的位置
    struct ArcNode *nextarc;    // 指向下一个邻接点的指针
} ArcNode;

// 邻接表中的顶点结点
typedef struct VNode {
    int data;           // 顶点数据
    ArcNode *firstarc;  // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 邻接表
typedef struct {
    AdjList vertices;   // 邻接表的顶点数组
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 创建邻接表
void createGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *p;

    // 输入顶点数和边数
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);

    // 输入顶点信息
    printf("请输入顶点信息：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }

    // 输入边信息
    printf("请输入边信息（起点 终点）：");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d%d", &i, &j);
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p;
    }
}

// 邻接表的广度优先搜索
void BFS(ALGraph *G, int v) {
    int i, w;
    ArcNode *p;
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;

    printf("%d ", G->vertices[v].data);
    visited[v] = TRUE;
    queue[rear++] = v;

    while (front != rear) {
        v = queue[front++];
        for (p = G->vertices[v].firstarc; p; p = p->nextarc) {
            w = p->adjvex;
            if (!visited[w]) {
                printf("%d ", G->vertices[w].data);
                visited[w] = TRUE;
                queue[rear++] = w;
            }
        }
    }
}

int main() {
    ALGraph G;
    int v;

    createGraph(&G);

    // 初始化 visited 数组
    for (v = 0; v < G.vexnum; v++) {
        visited[v] = FALSE;
    }

    printf("请输入起始顶点：");
    scanf("%d", &v);
    printf("广度优先搜索结果：");
    BFS(&G, v);

    return 0;
}

该示例代码首先定义了邻接表中的边结点 `ArcNode` 和顶点结点 `VNode`，以及邻接表 `ALGraph`。然后通过 `createGraph` 函数创建了一个邻接表，将输入的顶点和边信息存储到邻接表中。最后使用 `BFS` 函数实现了邻接表的广度优先搜索，并输出搜索结果。

在 `BFS` 函数中，首先将起始顶点 `v` 置为已访问，并将其加入队列中。然后从队列中取出一个顶点，遍历其所有邻接点，并将未访问的邻接点加入队列中。如此循环，直到队列为空，搜索结束。