6-2 邻接表存储图的广度优先遍历 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 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; //以邻接表存储的图类型
typedef struct QueueNode *PtrToQueueNode;
struct QueueNode //队列结点的定义
{
    Vertex Data; //存顶点下标
    PtrToQueueNode Next;
};
typedef PtrToQueueNode Queue; //队列类型
LGraph CreateGraph(int VertexNum) //初始化一个有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, Vertex V1, Vertex V2, WeightType Weight) //插入边
{
    PtrToAdjVNode NewNode;
    //插入边<V1, V2>
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = V2;
    NewNode->Weight = Weight;
    //头插法：将V2插入V1的表头
    NewNode->Next = Graph->G[V1].FirstEdge;
    Graph->G[V1].FirstEdge = NewNode;
    //若为无向图，还要插入边<V2, V1>
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = V1;
    NewNode->Weight = Weight;
    NewNode->Next = Graph->G[V2].FirstEdge;
    Graph->G[V2].FirstEdge = NewNode;
}
Queue CreateQueue() //创建空队列
{
    Queue Q;
    Q = (Queue)malloc(sizeof(struct QueueNode));
    Q->Next = NULL;
    return Q;
}
int IsEmpty(Queue Q) //判断队列Q是否为空
{
    return (Q->Next == NULL);
}
void Enqueue(Queue Q, Vertex V) //将顶点V插入队列
{
    PtrToQueueNode NewNode;
    NewNode = (PtrToQueueNode)malloc(sizeof(struct QueueNode));
    NewNode->Data = V;
    NewNode->Next = NULL;
    //将NewNode插入队列尾部
    while (Q->Next)
        Q = Q->Next;
    Q->Next = NewNode;
}
Vertex Dequeue(Queue Q) //将队头顶点弹出队列
{
    PtrToQueueNode FrontCell;
    Vertex FrontElem;
    if (IsEmpty(Q))
        return -1;
    else
    {
        FrontCell = Q->Next;
        if (Q->Next->Next == NULL)
            Q->Next = NULL;
        else
            Q->Next = Q->Next->Next;
        FrontElem = FrontCell->Data;
        free(FrontCell);
        return FrontElem;
    }
}
void Visit(Vertex V) //访问函数
{
    printf(" %d", V);
}
void BFS(LGraph Graph, Vertex S, void(*Visit)(Vertex)) //广度优先搜索
{
    Queue Q;
    Vertex V, W;
    PtrToAdjVNode P;
    Q = CreateQueue(); //创建空队列
    int visited[MaxVertexNum] = { 0 }; //初始化所有顶点为未访问
    Enqueue(Q, S); //将顶点S入队列
    visited[S] = 1; //标记S已访问
    while (!IsEmpty(Q))
    {
        V = Dequeue(Q); //弹出V
        Visit(V); //访问V
        for (P = Graph->G[V].FirstEdge; P; P = P->Next) //遍历V的所有邻接点
        {
            W = P->AdjV;
            if (!visited[W])
            {
                Enqueue(Q, W); //将未访问的邻接点W入队列
                visited[W] = 1; //标记W已访问
            }
        }
    }
}
int main()
{
    int N, M; //N为顶点数，M为边数
    scanf_s("%d %d", &N, &M); //读入顶点数和边数
    LGraph Graph = CreateGraph(N); //初始化图
    int V1, V2, Weight;
    for (int i = 0; i < M; i++)
    {
        scanf_s("%d %d %d", &V1, &V2, &Weight); //读入每条边的起点、终点和权重
        InsertEdge(Graph, V1 - 1, V2 - 1, Weight); //插入边
    }
    for (int i = 0; i < Graph->Nv; i++) //遍历每个顶点
    {
        if (!visited[i]) //如果该顶点未被访问
            BFS(Graph, i, Visit); //从该顶点开始广度优先搜索
    }
    return 0;
}

以上代码实现了基于邻接表存储图的广度优先遍历，其中 `CreateGraph()` 函数用于初始化一个有 `VertexNum` 个顶点但没有边的图，`InsertEdge()` 函数用于插入边，`BFS()` 函数用于进行广度优先搜索，`Visit()` 函数用于访问每个顶点。