图的邻接表表示

代码:

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

#define MaxVertexNum 100 // 最大顶点数设为 100
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; // Adjacency list --> 邻接表
struct AdjVNode {
    Vertex AdjV; // 邻接点下标
    WeightType Weight; // 边权重
    PtrToAdjVNode Next; // 指向下一个邻接点的指针
};

// 顶点表头节点的定义
typedef struct VNode {
    PtrToAdjVNode FirstEdge; // 边表头指针
    DataType Data; // 存顶点的数据
    // 注意, 很多情况下, 顶点无数据, 此时 Data 可以不用出现
} AdjList[MaxVertexNum]; // AdjList 是邻接表类型

// 图节点的定义
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; // 顶点数为 VertexNum
    Graph->Ne = 0; // 边数为 0
    // 初始化邻接表头指针
    // 注意: 这里默认顶点编号从 0 开始, 到(Graph->Nv - 1)
    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;

    scanf("%d", &Nv); // 读入顶点个数
    Graph = CreateGraph(Nv); // 初始化有 Nv 个顶点但没有边的图

    scanf("%d", &(Graph->Ne)); // 读入边数
    if (Graph->Ne != 0) { // 如果有边
        E = (Edge)malloc(sizeof(struct ENode));
        // 读入边, 格式为 "起点, 终点, 权重", 插入邻接表
        for (i = 0; i < Graph->Ne; i++)
        {
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            // 注意: 如果权重不是整型, Weight 的读入格式要改
            InsertEdge(Graph, E);
        }
    }

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

    return Graph;
}

// 简单遍历图
void PrintGraph(LGraph Graph)
{
    if (!Graph->G[0].FirstEdge) // 邻接表为空
        return;

    int i;
    for (i = 0; i < Graph->Nv; i++)
    {
        printf("%d: | ", i);

        PtrToAdjVNode tmp = Graph->G[i].FirstEdge;

        while (tmp)
        {
            printf("%d %d | ", tmp->AdjV, tmp->Weight);
            tmp = tmp->Next;
        }
        printf("
");
    }
}

// 测试一组数据, 测试的图有 5 个顶点, 8 条有向边
// <1, 0, 9> <0, 2, 6> <2, 4, 7> <4, 3, 6>
// <3, 1, 5> <1, 2, 4> <0, 3, 3> <3, 4, 8>
int main()
{
    LGraph Graph = BuildGraph();
    PrintGraph(Graph);

    return 0;
}

// 测试数据
/*
5
8
1 0 9
0 2 6
2 4 7
4 3 6
3 1 5
1 2 4
0 3 3
3 4 8
*/

输出结果:

关于上面的输出结果的说明:

每一行的第一个数字代表顶点序号, 然后每两个竖线之间存储的分别是和该顶点相连接的顶点序号和它们之间的权值.

图的示意:

参考:《数据结构第 2 版》(陈越) & 浙江大学数据结构 MOOC