图结构_邻接表

结构 - 边 ENode - PtrToENode - Edge

1. 1.无向边(V1,V2),V1 V2为顶点
2. 权重Weight

结构 - 邻接点 AdjVNode - PtrToAdjVNode

1. 邻结点下标AdjV
2. 邻结点权重Weight
3. 下一个邻接点Next

结构 - 头结点 Vnode - AdjList

1. 边表头指针,第一个邻接点FirstEdge
2. 顶点的数据Data
3. Vnode类型的顶点数组AdjList

结构 - 图结点 GNode - PtrToGNode - LGraph

1. 图的顶点数Nv,边数Ne
2. 邻接表，所有表头结点AdjList的数组G

编码

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#define MaxVertexNum 100

typedef int Vertex;// 用整形表示顶点
typedef int WeightType; // 权重
typedef char DataType;// 顶点数据，字符型
bool Visited[MaxVertexNum];

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
//边的定义
struct ENode {
    //1.无向边(V1,V2),V1 V2为顶点
    Vertex V1, V2;
    //2.权重Weight
    WeightType Weight;
};

typedef struct AdjVNode *PtrToAdjVNode;
// 邻接点的定义
struct AdjVNode {
    //1.邻结点下标
    Vertex AdjV;
    //2.邻结点权重
    WeightType Weight;
    //3.下一个邻接点
    PtrToAdjVNode Next;
};

// 表头结点的定义
typedef struct Vnode {
    // 1.边表头指针,第一个邻接点
    PtrToAdjVNode FirstEdge;
    // 2.顶点的数据
    DataType Data;
} AdjList[MaxVertexNum]; // 3.Vnode类型的顶点数组

typedef struct GNode *PtrToGNode;
// 图结点
struct GNode {
    // 1.图的顶点数Nv,边数Ne
    int Nv, Ne;
    // 2.邻接表，所有表头结点的数组 - 链表
    AdjList G;
};
typedef PtrToGNode LGraph;

//创建零图
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;
        // 初始化结点未被访问
        Visited[V] = false;
    }
    return Graph;
}

// 插入边E<V1,V2>
void InsertEdge(LGraph Graph, Edge E) {
    // 1.动态申请邻接点NewNode
    PtrToAdjVNode NewNode;
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    // 2.将边E的终点V2填入NewNode中AdjV，及权重Weight
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    // 3.将新的邻边结点NewNode插入起始点V1的表头
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    // 4.如果E是无向边，同样需要插入V2为始点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;
    //1.读取顶点数Nv
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    //2.读取边数Ne
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0) {
        E = (Edge) malloc(sizeof(struct ENode));
        // 3.循环读入边的数据
        for (i = 0; i < Graph->Ne; i++) {
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            InsertEdge(Graph, E);
        }
    }
    // 4.输入顶点数据Data
    for (V = 0; V < Graph->Nv; V++) {
        scanf("%c", &(Graph->G[V].Data));
    }
    return Graph;
}

void Visit(Vertex V) {
    printf("正在访问顶点%d\n", V);
}

//邻接表深度优先搜索
void DFS(LGraph Graph, Vertex V, void(*Visit)(Vertex)) {
    PtrToAdjVNode W;
    // 1.先访问邻结点V
    Visit(V);
    Visited[V] = true;
    // 2.遍历搜索下一个邻接点
    for (W = Graph->G[V].FirstEdge; W; W = W->Next) {
        //3.如果W未访问过，递归访问DFS
        if (!Visited[W->Next->AdjV])
            DFS(Graph, W->Next->AdjV, Visit);
    }
}

//邻接表的广度优先搜索
void BFS(LGraph Graph, Vertex S, void(*Visit)(Vertex)) {
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;
    //1.创建队列Q，并将结点S加入队列
    Q = CreateQueue(MaxSize);
    Visit(S);
    Visited[S] = true;
    AddQ(Q, S);
    // 2.遍历队列直到为空
    while (!IsEmpty(Q)) {
        // 3.从队头删除元素V
        V = DeleteQ(Q);
        // 4.遍历与V相邻的所有顶点
        for (W = Graph->G[S].FirstEdge; W; W = W->Next) {
            // 5.如果未访问过,则访问该顶点，同时加入队列
            if (!Visited[W->Next]) {
                Visit(W);
                Visited[W] = true;
                AddQ(Q, W);
            }
        }
    }
}

// 无权图 - 无权图的单源最短路算法
void UnWeighted(LGraph Graph, int dist[], int path[], Vertex S) {
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;
    // 创建空队列, MaxSize为外部定义的常数
    Q = CreateQueue(Graph->Nv);
    //初始化源点
    dist[S] = 0;
    AddQ(Q, S);
    while (!IsEmpty(Q)) {
        V = DeleteQ(Q);
        //对V的每个邻接点W->AdjV
        for (W = Graph->G[V].FirstEdge; W; W = W->Next) {
            // 若W->AdjV未被访问过
            if (dist[W->AdjV] == -1) {
                //W->AdjV到S的距离更新
                dist[W->AdjV] = dist[V] + 1;
                // 将V记录在S到W->AdjV的路径上
                path[W->AdjV] = V;
                AddQ(Q, W->AdjV);
            }
        }
    }
}