1. 前言

图是一种非线性数据结构,是一种更为复杂的数据结构,在图中,数据元素之间时多对多的关系,即一个数据元素对应多个直接前驱和多个直接后继元素。图的应用领域十分广泛,如化学分析,工程设计、遗传学、人工智能等。

2. 图的定义和相关概念

图是一种数据元素间为多对多关系的数据结构,加上一组基本操作构成的抽象数据类型。

数据对象V :V是具有相同特性的数据元素的集合,称为顶点集。

数据关系R:

R={VR}

VR={<v,w>|v,w(-V且P(v,w),<v,w>表示从v到w的弧,谓词P(v,w)定义了弧<v,w>的意义或信息}

基本操作P:

  • CreateGraph(&G,V,VR)
    • 初始条件:V是图的顶点集,VR是图中弧的集合。
    • 操作结果:按V和VR的定义构造图G
  • DestroyGraph(&G);
    • 初始条件:图G存在
    • 操作结果:销毁图G
  • LocateVex(G,u);
    • 初始条件:图G存在,u一G中顶点有相同特征
    • 操作结果:若G中存在顶点u, 则返回该顶点在图中位置;否则返回其它信息。
  • GetVex(G,v);
    • 初始条件:图G存在,v是G中某个顶点
    • 操作结果:返回v的值。
  • PutVex(&G,v,value);
    • 初始条件:图G存在,v是G中某个顶点
    • 操作结果:对v赋值value
  • FirstAdjVex(G,v);
    • 初始条件:图G存在,v是G中某个顶点
    • 操作结果:返回v的第一个邻接顶点。若顶点在G中没有邻接顶点,则返回“空”
  • NextAdjVex(G,v,w);
    • 初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点。
    • 操作结果:返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点,则返回“空”
  • InsertVex(&G,v);
    • 初始条件:图G存在,v和图中顶点有相同特征
    • 操作结果:在图G中增添新顶点v
  • DeleteVex(&G,v);
    • 初始条件:图G存在,v是G中某个顶点
    • 操作结果:删除G中顶点v及其相关的弧
  • InsertAcr(&G,v,w);
    • 初始条件:图G存在,v和w是G中两个顶点
    • 操作结果:在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
  • DeleteArc(&G,v,w);
    • 初始条件:图G存在,v和w是G中两个顶点
    • 操作结果:在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>
  • DFSTraverser(G,v,Visit());
    • 初始条件:图G存在,v是G中某个顶点,Visit是顶点的应用函数
    • 操作结果:从顶点v起深度优先遍历图G,并对每个顶点调用函数Visit一次。一旦Visit()失败,则操作失败。
  • BFSTRaverse(G,v,Visit());
    • 初始条件:图G存在,v是G中某个顶点,Visit是顶点的应用函数
    • 操作结果:从顶点v起广度优先遍历图G,并对每个顶点调用函数Visit一次。一旦Visit()失败,则操作失败。

    

图 有向图和无向图

对上图有:G1=(V1,{A1})

其中:V1={v1,v2,v3,v4} A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}

如果用n表示图中顶点数目,用e表示边或弧的数目,则有:

对于无向图,e的取值范围是0到n(n-1)/2,有n(n-1)/2条边的无向图称为完全图。

对于有向图,e有取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。

有很少条边或弧的图称为稀疏图,反之称为稠密图。

3. 图的存储结构

图的存储方式有四种:邻接矩阵表示法、邻接表表示法、十字链表表示法和多重链表表示法。

(1)邻接矩阵表示法

图的邻接矩阵表示也称为数组表示,图的邻接矩阵就是利用C语言中的两个数组实现。其中一个是一维数组,用来存储图中的顶点信息;另一个是二维数组,用来存储图中的顶点之间的关系,该二维数组被称为邻接矩阵。

图的邻接矩阵表示法也称为数组表示。如果图式一个无权图,则邻接矩阵表示为:

对于带权图,有

上图的邻接矩阵表示如下图所示:

图的邻接矩阵存储结构用C语言描述如下:

 

C代码  收藏代码
  1. #define INFINITY 10000      /*定义一个无限大的值*/
  2. #define MaxSize 50          /*最大顶点个数*/
  3. typedef enum{DG,DN,UG,UN}GraphKind;     /*图的类型:有向图、有向网、无向图和无向网*/
  4. typedef struct
  5. {
  6.     VRType adj;         /*对于无权图,用1表示相邻,0表示不相邻;对于带权图,存储权值*/
  7.     InfoPtr *info;          /*与弧或边的相关信息*/
  8. }ArcNode,AdjMatrix[MaxSize][MaxSize];
  9. typedef struct              /*图的类型定义*/
  10. {
  11.     VertexType vex[MaxSize];    /*用于存储顶点*/
  12.     AdjMatrix arc;              /*邻接矩阵,存储边或弧的信息*/
  13.     int vexnum,arcnum;          /*顶点数和边(弧)的数目*/
  14.     GraphKind kind;             /*图的类型*/
  15. }MGraph;

 

带权图的邻接矩阵表示示意图:

(2)邻接表表示法

图的邻接表表示法是一种链式存储方式。在图的邻接表中,对图中的每个顶点都建立一个单链表,用来表示边或弧,这种表示顶点之间关系的链表称为边表,相应地,结点称为边结点。在每个单链表前面设置一个头结点,存放图中的各个顶点结点,这种表称为表头结点表,相应地,结点称为表头结点。

图的邻接表存储结构可以用C语言描述如下:

C代码  收藏代码
  1. #define MaxSize 50          /*最大顶点个数*/
  2. typedef enum{DG,DN,UG,UN}GraphKind;     /*图的类型:有向图、有向网、无向图和无向网*/
  3. typedef struct ArcNode      /*边结点的类型定义*/
  4. {
  5.     int adjvex;             /*弧指向的顶点的位置*/
  6.     InfoPtr *info;          /*与弧相关的信息*/
  7.     struct ArcNode *nextarc;    /*指示下一个与该顶点相邻接的顶点*/
  8. }ArcNode;
  9. typedef struct VNode        /*头结点的类型定义*/
  10. {
  11.     VertexType data;        /*用于存储顶点*/
  12.     ArcNode *firstarc;      /*指示第一个与该顶点邻接的顶点*/
  13. }VNode,AdjList[MaxSize];
  14. typedef struct              /*图的类型定义*/
  15. {
  16.     AdjList vertex;
  17.     int vexnum,arcnum;      /*图的顶点数目与弧的数目*/
  18.     GraphKind kind;         /*图的类型*/
  19. }AdjGraph;

 

(3)十字链表表示法(有向图)

十字链表是有向图的又一种链式存储结构,它是将有向图的邻接表与逆邻接链表结合起来的存储结构表示。因此,在十字链表中,同样包括表头结点和边结点。在十字链表中,将表头结点称为顶点结点,边结点称为弧结点。

 

有向图的十字链表存储结构可以用C语言描述如下:

C代码  收藏代码
  1. #define MaxSize 50              /*最大顶点个数*/
  2. typedef struct ArcNode          /*弧结点的类型定义*/
  3. {
  4.     int headvex,tailvex;            /*弧的头顶点和尾顶点位置*/
  5.     InfoPtr *info;              /*与弧相关的信息*/
  6.     struct *hlink,*tlink;           /*指示弧头和弧尾相同的结点*/
  7. }ArcNode;
  8. typedef struct VNode            /*顶点结点的类型定义*/
  9. {
  10.     VertexType data;            /*用于存储顶点*/
  11.     ArcNode *firstin,*firstout;         /*分别指向顶点的第一条入弧和出弧*/
  12. }VNode;
  13. typedef struct                  /*图的类型定义*/
  14. {
  15.     VNode vertex[MaxSize];
  16.     int vexnum,arcnum;      /*图的顶点数目与弧的数目*/
  17. }OLGraph;

 

(4)邻接多重链表表示法(无向图)

邻接多重链表表示是无向图的另一种链式存储结构。在无向图的邻接表存储表示中,虽然可以很容易对邻接表进行操作,但是图的每一条边在邻接表中需要存储两个结点,如果要检查某个边是否被访问过,则需要在邻接表中找到两个结点。而邻接多重表是将图的一条边用一个结点表示。

无向图的多重链表存储结构可以用C语言描述如下:

C代码  收藏代码
  1. #define MaxSize 50              /*最大顶点个数*/
  2. typedef struct EdgeNode         /*边结点的类型定义*/
  3. {
  4.     int mark,ivex,jvex;             /*访问标志和边的两个顶点位置*/
  5.     InfoPtr *info;              /*与边相关的信息*/
  6.     struct *ilink,*jlink;           /*指示与边顶点相同的结点*/
  7. }EdgeNode;
  8. typedef struct VNode            /*顶点结点的类型定义*/
  9. {
  10.     VertexType data;            /*用于存储顶点*/
  11.     EdgeNode *firstedge;        /*指向依附于顶点的第一条边*/
  12. }VexNode;
  13. typedef struct                  /*图的类型定义*/
  14. {
  15.     VexNode vertex[MaxSize];
  16.     int vexnum,edgenum;     /*图的顶点数目与边的数目*/
  17. }AdjMultiGraph;