邻接表的方法实现图的广度优先遍历 C语言

以下是C语言实现邻接表存储图的广度优先遍历的方法：

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

#define MaxVertexNum 100 // 最大顶点数
#define INFINITY 65535 // 无穷大

typedef int Vertex; // 顶点类型
typedef int WeightType; // 权重类型
typedef char DataType; // 数据类型

// 边的定义
typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1, V2; // 有向边<V1, V2>
    WeightType Weight; // 权重
};
typedef PtrToENode Edge;

// 邻接点的定义
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
    Vertex AdjV; // 邻接点下标
    WeightType Weight; // 权重
    PtrToAdjVNode Next; // 指向下一个邻接点的指针
};

// 顶点的定义
typedef struct Vnode {
    PtrToAdjVNode FirstEdge; // 指向第一个邻接点的指针
    DataType Data; // 存顶点的数据
} AdjList[MaxVertexNum];

// 图的定义
typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv; // 顶点数
    int Ne; // 边数
    AdjList G; // 邻接表
};
typedef PtrToGNode LGraph;

// 初始化一个有VertexNum个顶点但没有边的图
LGraph CreateGraph(int VertexNum) {
    Vertex V;
    LGraph Graph;

    Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;

    // 初始化邻接表头指针
    for (V = 0; V < Graph->Nv; V++)
        Graph->G[V].FirstEdge = NULL;

    return Graph;
}

// 插入边
void InsertEdge(LGraph Graph, Edge E) {
    PtrToAdjVNode NewNode;

    // 插入边<V1, V2>
    // 为V2建立新的邻接点
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    // 将V2插入V1的表头
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    // 若是无向图，还要插入边<V2, V1>
    // 为V1建立新的邻接点
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    // 将V1插入V2的表头
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

// 建立图并插入边
LGraph BuildGraph() {
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;

    printf("请输入顶点数：");
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);

    printf("请输入边数：");
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        printf("请输入每条边的起点、终点和权重：\n");
        for (i = 0; i < Graph->Ne; i++) {
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            InsertEdge(Graph, E);
        }
    }

    // 如果顶点有数据的话，读入数据
    for (V = 0; V < Graph->Nv; V++)
        scanf(" %c", &(Graph->G[V].Data));

    return Graph;
}

// 遍历图
void BFS(LGraph Graph, Vertex S, void (*Visit)(Vertex)) {
    int queue[1000], f = 0, r = 0;
    int Visited[MaxVertexNum] = {0}; // 访问标记数组
    PtrToAdjVNode temp;

    queue[r++] = S;
    Visited[S] = 1;
    Visit(S);

    while (f != r) {
        temp = Graph->G[queue[f++]].FirstEdge;
        while (temp) {
            int x = temp->AdjV;
            if (!Visited[x]) {
                Visited[x] = 1;
                Visit(x);
                queue[r++] = x;
            }
            temp = temp->Next;
        }
    }
}

// 打印顶点
void PrintVertex(Vertex V) {
    printf("%d ", V);
}

int main() {
    LGraph Graph;
    Vertex S;

    Graph = BuildGraph();

    printf("请输入遍历起点：");
    scanf("%d", &S);
    printf("广度优先遍历结果：");
    BFS(Graph, S, PrintVertex);

    return 0;
}