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

基础知识

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};
邻接矩阵:

V1V2V3V4
V111
V21
V311
V4111

这里的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中分配。(边的创建实际上就是链表的创建)

之前用无向图作为无向网举例,这次用有向图作为有向网举例(图和网的区别在于边/弧是否有权重):

序号顶点信息第一条弧指向第二条弧指向
0-101NULL
102NULL
213NULL
3-51NULL

顶点信息:
V1: -10
V2: 0
V3: 1
V4: -5

各边权重:
V1->V2: 2
V2->V3: 3
V3->V4: 5
V4->V2: 7

十字链表表示法

结构

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

存储弧的结构体: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)这整个过程中,顶点的出弧与入弧会变化,当有弧以这个顶点作为弧尾/弧头时。

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注