数据结构简单入门/复习（七）-图的代码示例（C语言）

2022/1/24：更新为 Markdown 格式，修改图对应描述，修改代码及图格式。

基础知识

enum day {Mon, Tue, Wed, Thu, Fri, Sat, Sun}; //表示定义一个枚举类型，类似#define Mon 0 #define Tue 1 #define Wed 2，以此类推
如果想让Mon为1，Tue为2，则
enum day {Mon=1, Tue, Wed, Thu, Fri, Sat, Sun};
枚举中的每个元素依次加一，但也可以跳过一些数：
enum day {Mon=1, Tue, Wed, Thu=14, Fri, Sat, Sun};
则对应的值分别为1，2，3，14，15，16，17

枚举enum的使用方式与struct结构体类似，在定义类型时也可以定义变量

enum Day {
 Mon, Tue, Wed, Thu, Fri, Sat, Sun
}day;

表示定义一个Day类型的day变量。

数组表示法/邻接矩阵表示法

结构

原理：用两个数组分别存储数据元素的信息与数据元素之间的关系。

构造两个结构体，
一个以二维数组的矩阵形式存储各边/弧之间的关系：
如果是没有附加信息的无向图，则存储边是否存在即可，因为是边，所以存储的时候矩阵的下三角是与上三角相同的（i到j = j到i）。
如果是附加信息的有向网，则需存储边的权重，以及额外信息，因为是弧，所以i到j与j到i的权值不一定相同。
有向图、有向网、无向图、无向网 ，四个不同类型的图，在矩阵存储时的区别只在于边的关系不同，即下方代码的VRType adj;不同。

另一个结构体存储顶点、邻接矩阵（上面的结构体）、当前顶点数、当前边/弧数目，以及图的种类。
当然，在实际使用时图的种类可以直接用不同的结构体替代，但不同图的结构在邻接矩阵表示中是一样的，所以可以直接用一种结构表示四种图，加上标识即可。

#define MAX_VERTEX_NUM 20                    //最大顶点个数
typedef enum {DG, DN, UDG, UDN} GraphKind;   //{有向图、有向网、无向图、无向网}

typedef struct{
    VRType     adj;        //VRType是顶点关系类型，无向图用0/1表示是否相邻，带权图则是权值类型
    InfoType   *info;    //弧的相关信息指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM, MAX_VERTEX_NUM];

typedef struct{
    VertexType vex[MAX_VERTEX_NUM];    //顶点向量
    AdjMatrix  arcs;                   //邻接矩阵，注意该类型是二维数组
    int        vexnum, arcnum;         //图的当前顶点数与弧/边的数目
    GraphKind  kind;                   //图的种类标志
}MGraph;

创建无向网

对于下面的无向图，将其当做各边权值为1的无向网，则使用下面的代码创建后，将会生成：
顶点向量：vex[]={1,2,3,4};
邻接矩阵：

这里的V1~V4四个顶点的数据分别为1、2、3、4。

#define INFINITY INT_MAX    //定义初始化值/最大值,INT_MAX为C语言的常量，是整形的最大上限

MGraph G;
createGraph(&G);

void createGraph(MGraph *G)    //选择创建的图的类型
    scanf(%d,&G->kind);
    switch(G->kind){
        case DG:     return createDG(G);
        case DN:     return createDN(G);
        case UDG:    return createUDG(G);
        case UDN:    return createUDN(G);
        default:     return ERROR;
}

void createUDN(MGraph *G){
    scanf(%d%d%d, &G->vexnum, &G->arcnum, &IncInfo);    //输入顶点个数、边个数。IncInfo表示各边是否含其他信息。
    for(i=0; i<G->vexnum; i++)                   //输入顶点向量
        scanf(%d, G->vex[i]);
    for(i=0; i<G->vexnum; i++)                   //初始化边
        for(j=0; j<G->vexnum; j++)
            G->arcs[i][j] = INFINITY;
    for(k=0; k<G->arcnum;k++){                   //输入边的信息
        int i, j, weight;
        scanf(%d%d%d, &i, &j, &weight);        //输入一条边依附的两个顶点位置，与边的权值。这里的顶点位置也可以通过输入顶点信息，然后查询位置获得，这里简化
        G->arcs[i][j] = G->arcs[j][i] = weight;  //设置边的权值，对于无向图，i到j与j到i的线段没有方向，是同一条边。
        if(IncInfo) {                            //如果边有其他信息，则输入
            scanf(%d, G->arcs[i][j]->info);    //本示例的info是指针类型，所以没有&。
            G->arcs[j][i] = G->[i][j];
        }
    }
} 

邻接表表示法

结构

原理：定义三个结构体，

一个以链表方式存储边的信息，需要存储 1.指向哪个顶点 2.下一条边/弧的地址 3.额外的数据（如果有）。其中（如果对第二条有疑问），下一条边/弧指的是起点相同，终点不同的边，例如，A有两条边，一条是AB，一条是AC，如果第一条是AB，那么第二条边就是AC，这个顺序可以颠倒。

另一个类似链表的头结点，它存储顶点的数据信息、以及指向第一条边/弧的指针。

最后一个是存储整个图的结构体，需要存储所有顶点（用数组方式）、顶点数目、边/弧的数目、以及图的类型。

#define MAX_VERTEX_NUM 20
typedef struct{           //边/弧类型
    int             adjvex;       //顶点位置
    struct ArcNode  *nextArc;     //指向下一条边/弧
    InfoType        *info;        //存储额外信息的指针
}ArcNode;

typedef struct{              //顶点类型
    VertexType data;               //顶点信息
    ArcNode    *firstArc;          //指向第一个边/弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{                     //图类型
    AdjList    vertices;            //顶点数组
    int        vexnum, arcnum;      //顶点、边/弧数目
    int        kind;                //图的类型
}ALGraph;

示例

能到图这一块，对于这种简单数据结构的创建，只要明白其存储方式，创建起来很容易，因此，这里讲解一下创建过程，之后直接给出创建示例。
顺便满足下我的怠惰之心。

首先定义一个图，输入图的类型、顶点与边/弧数目，并根据顶点数目创建一个顶点类型的数组。
之后，对于每个顶点信息进行输入，先输入顶点的信息，然后用malloc方法给顶点的first边/弧分配空间，如果还有边，在firstArc的nextArc中分配。（边的创建实际上就是链表的创建）

之前用无向图作为无向网举例，这次用有向图作为有向网举例（图和网的区别在于边/弧是否有权重）：

十字链表表示法

结构

原理：十字链表表示法是有向图/有向网的结构，类似将邻接表与逆邻接表结合起来。
由三个结构体组成：

存储弧的结构体：1.存储弧尾与弧头的顶点位置。 2. 3.同一个弧头、弧尾的下一条弧。 4.弧的额外信息。

存储顶点的结构体：1.顶点数据。 2. 3.指向该顶点的第一条入弧、出弧（类似链表的头结点）

存储图的结构体：1. 存储顶点的数组 2. 3.当前顶点数、弧数目

#define MAX_VERTEX_NUM 20
typedef struct{                           //弧类型
    int              tailVex, headVex;    //弧的尾、头结点位置（弧从尾指向头，因此在本结构中tail在前）
    struct arcBox    *hLink, *tLink;      //指向下一条弧的头、尾相同的的指针
    InfoType         *info;               //弧的额外信息存储指针
}arcBox;

typedef struct{                            //顶点类型
    VertexType   data;                     //顶点数据
    arcBox       *firstIn, *firstOut;      //指向该顶点的第一条入弧、出弧
}VexNode;

typedef struct{                             //图类型
    VexNode      vex[MAX_VERTEX_NUM];       //顶点存储数组
    int          vexnum, arcnum;            //当前顶点数、弧数目
}OLGraph;

创建有向图

为了给各位增添更多的负担，我这里提供一个简单但是头疼的算法。
算法原理和下面的例子一起了，粗体字部分是关键，斜体是关键的关键。
（不包括输入额外信息的，添加额外信息的代码和前面一样，给个是否输入的条件，然后给弧的info添加上就好了）：

OLGraph G;
scanf(%d%d%d, &G.vexnum, &G.arcnum);              //输入顶点数、弧数目
for(i=0; i<G.vexnum; i++){                          //初始化顶点
    scanf(%d, &G.vex[i].data);                    //顶点信息输入
    G.vex[i].firstIn = G.vex[i].firstOut = NULL;    //顶点第一条出入弧置NULL
}
for(k=0; k<G.arcnum; k++){
    int i, j;
    scanf(%d%d, &i, &j);                          //弧的尾i，头j位置输入。也可以通过输入弧尾/头数据，然后再获取其位置，这里简化
    arcBox *p = (arcBox*)malloc(sizeof(acrBox));
    p = {i, j, G.vex[j].firstIn, G.vex[i].firstOut, NULL}    //分别是弧尾、弧头、弧头的第一条入弧、弧尾的第一条出弧、空的额外信息
    G.vex[j].firstIn = G.vex[i].firstOut = p;        //
} 

这次用有向图举例：

建立了一个图G，输入顶点数和弧数目之后，开始输入各顶点的信息。
之后进行弧的插入，输入弧尾、弧头，定义一个临时变量存储弧信息，弧尾与弧头设置好。

然后，设置firstIn与firstOut，这是比较难理解的地方：
首先创建V1->V2弧（这里序号以1开始，方便区分），
设置完弧尾弧头，
此时头顶点2的入弧是NULL，将hLink，即下一条弧的指针设置为入弧NULL。
再将尾顶点1的出弧NULL，作为tLink，即下一条弧的指针。
然后将 头顶点2入弧 与 尾顶点1出弧 设置为V1->V2弧。

之后创建第二条弧V2->V3，弧尾弧头设置完，
此时头顶点3入弧NULL，设置成该弧的hLink，
再将尾顶点2出弧NULL，设置成该弧的tLink.
3入弧，2出弧设置为V2->V3。

第三条弧V3->V4，弧尾弧头设置完，
此时头顶点4入弧NULL，设置成该弧的hLink，
再将尾顶点3出弧NULL，设置成该弧的tLink.
4入弧，3出弧设置为V3->V4。

第四条弧V4->V2，弧尾弧头设置完，
头结点2入弧是V1->V2弧，将该弧的hLink设置成V1->V2弧，此时可以看出，出现了两条有相同弧头的弧，这就是这个算法的关键：通过弧B的出现，将与弧B有着的同一个弧尾的弧A，设置成弧B的下一条弧，再将弧B设置成这个弧尾的出弧（即替换弧尾出弧的弧A)，这整个过程中，顶点的出弧与入弧会变化，当有弧以这个顶点作为弧尾/弧头时。