图的特性

图(Graph)是一种比线性表和树更为复杂的数据结构。 线性结构：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。 树结构：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。 图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。

图的基本概念

图、顶点、弧

一个图(G)定义为一个偶对(V,E) ，记为G=(V,E) 。其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&V的一个子集，记为E(G) ，其元素是图的弧(Arc)。 将顶点集合为空的图称为空图。其形式化定义为：

1. G=(V ，E)
2. V={v|vdata object}
3. E={<v,w>| v,wV∧p(v,w)} P(v,w)表示从顶点v到顶点w有一条直接通路。

弧(Arc) ：表示两个顶点v和w之间存在一个关系，用顶点偶对<v,w>表示。通常根据图的顶点偶对将图分为有向图和无向图。

有向图、无向图

有向图(Digraph)： 若图G的关系集合E(G)中，顶点偶对<v,w>的v和w之间是有序的，称图G是有向图。 在有向图中，若 <v,w>E(G) ，表示从顶点v到顶点w有一条弧。 其中：v称为弧尾(tail)或始点(initial node)，w称为弧头(head)或终点(terminal node)。 无向图(Undigraph)： 若图G的关系集合E(G)中，顶点偶对<v,w>的v和w之间是无序的，称图G是无向图。 在无向图中，若<v,w>属于E(G) ，有<w,v>属于E(G) ，即E(G)是对称，则用无序对(v,w) 表示v和w之间的一条边(Edge)，因此(v,w) 和(w,v)代表的是同一条边。

完全有向图、完全无向图

完全无向图：对于无向图，若图中顶点数为n ，用e表示边的数目，则e属于[0，n(n-1)/2] 。具有n(n-1)/2条边的无向图称为完全无向图。 完全无向图另外的定义是： 对于无向图G=(V，E)，若任意的vi，vj属于V ，当vi≠vj时，有(vi ,vj)属于E，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。

完全有向图：对于有向图，若图中顶点数为n ，用e表示弧的数目，则e属于[0，n(n-1)] 。具有n(n-1)条边的有向图称为完全有向图。 完全有向图另外的定义是： 对于有向图G=(V，E)，若任意的vi，vj属于V ，当vi ≠vj时，有<vi ,vj>属于E∧<vj , vi >属于E ，即图中任意两个不同的顶点间都有一条弧，这样的有向图称为完全有向图。

稀疏图、稠密图

有很少边或弧的图（e<n㏒n）的图称为稀疏图，反之称为稠密图。

权

权(Weight)：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。

子图、生成子图

子图和生成子图：设有图G=(V，E)和G’=(V’，E’)，若V’含于V且E’含于E ，则称图G’是G的子图；若V’=V且E’含于E，则称图G’是G的一个生成子图。 顶点的邻接(Adjacent)：对于无向图G=(V，E)，若边(v,w)属于E，则称顶点v和w 互为邻接点，即v和w相邻接。边(v,w)依附(incident)于顶点v和w 。 对于有向图G=(V ，E)，若有向弧<v,w>属于E，则称顶点v “邻接到”顶点w，顶点w “邻接自”顶点v ，弧<v,w> 与顶点v和w “相关联” 。

顶点的度、入度、出度

对于无向图G=(V，E)，任意的vi属于V，图G中依附于vi的边的数目称为顶点vi的度(degree)，记为TD(vi)。 显然，在无向图中，所有顶点度的和是图中边的2倍。 即 ∑TD(vi)=2e i=1, 2, …, n ，e为图的边数。 对有向图G=(V，E)，若任意的vi属于V ，图G中以vi作为起点的有向边(弧)的数目称为顶点vi的出度(Outdegree)，记为OD(vi) ；以vi作为终点的有向边(弧)的数目称为顶点vi的入度(Indegree)，记为ID(vi) 。顶点vi的出度与入度之和称为vi的度，记为TD(vi) 。即TD(vi)=OD(vi)+ID(vi)

路径(Path)、路径长度、回路(Cycle)

对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。 对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。

或路径是图G中连接两顶点之间所经过的顶点序列。即
Path=vi0vi1…vim ，vij属于V且(vij-1, vij)属于E j=1,2, …,m 或
Path=vi0vi1 …vim ，vij属于V且<vij-1, vij>属于E j=1,2, …,m 路径上边或有向边(弧)的数目称为该路径的长度。 在一条路径中，若没有重复相同的顶点，该路径称为简单路径； 第一个顶点和最后一个顶点相同的路径称为回路(环)； 在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。

连通图、图的连通分量

对无向图G=(V，E)，若任意的vi ，vj属于V，vi和vj都是连通的，则称图G是连通图，否则称为非连通图。若G是非连通图，则极大的连通子图称为G的连通分量。 对有向图G=(V，E)，若任意的vi ，vj属于V，都有以vi为起点， vj 为终点以及以vj为起点，vi为终点的有向路径，称图G是强连通图，否则称为非强连通图。若G是非强连通图，则极大的强连通子图称为G的强连通分量。 “极大”的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。

生成树、生成森林

一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。 关于无向图的生成树的几个结论：

• 一棵有n个顶点的生成树有且仅有n-1条边；
• 如果一个图有n个顶点和小于n-1条边，则是非连通图；
• 如果多于n-1条边，则一定有环；
• 有n-1条边的图不一定是生成树。

有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。 有向树是只有一个顶点的入度为0 ，其余顶点的入度均为1的有向图，

网

每个边(或弧)都附加一个权值的图，称为带权图。带权的连通图(包括弱连通的有向图)称为网或网络。网络是工程上常用的一个概念，用来表示一个工程或某种流程。

图的存储结构

图的存储结构比较复杂，其复杂性主要表现在：

• 任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。
• 图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。

图的常用的存储结构有：邻接矩阵、邻接链表、十字链表、邻接多重表和边表。

邻接矩阵(数组)表示法

基本思想：对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。

无向图的邻接矩阵（数组）表示

无权图的邻接矩阵

无向无权图G=(V，E)有n(n≧1)个顶点，其邻接矩阵是n阶对称方阵，其元素的定义如下：

带权图的邻接矩阵

其元素的定义如下：

无向图邻接矩阵的特性

如下：

• 邻接矩阵是对称方阵；
• 对于顶点vi，其度数是第i行的非0元素的个数；
• 无向图的边数是上(或下)三角形矩阵中非0元素个数。

有向图的数组表示

无权图的邻接矩阵

若有向无权图G=(V，E)有n(n≧1)个顶点，则其邻接矩阵是n阶对称方阵，元素定义如下：

带权图的邻接矩阵

有向带权图G=(V，E)的邻接矩阵其元素的定义如下：

有向图邻接矩阵的特性

如下：

• 对于顶点vi，第i行的非0元素的个数是其出度OD(vi)；第i列的非0元素的个数是其入度ID(vi) 。
• 邻接矩阵中非0元素的个数就是图的弧的数目。

图的邻接矩阵的存储结构

图的邻接矩阵的实现比较容易，定义两个数组分别存储顶点信息(数据元素)和边或弧的信息(数据元素之间的关系) 。其存储结构形式定义如下：

#define INFINITY  MAX_VAL     /* 最大值∞ */
/* 根据图的权值类型，分别定义为最大整数或实数 */
#define MAX_VEX  30     /*  最大顶点数目 */
typedef enum {DG, AG, WDG,WAG} GraphKind ;
/*  {有向图，无向图，带权有向图，带权无向图}  */
typedef struct ArcType
{  VexType  vex1, vex2 ;    /*  弧或边所依附的两个顶点 */
   ArcValType  ArcVal ;     /*  弧或边的权值  */
   ArcInfoType  ArcInfo ;   /*  弧或边的其它信息   */
} ArcType ;   /*  弧或边的结构定义  */
typedef struct
{  GraphKind  kind ;    /*  图的种类标志   */
   int  vexnum , arcnum ;   /*  图的当前顶点数和弧数  */
   VexType   vexs[MAX_VEX] ;  /*  顶点向量  */
   AdjType   adj[MAX_VEX][MAX_VEX];
} MGraph ;    /*  图的结构定义   */

利用上述定义的数据结构，可以方便地实现图的各种操作。

邻接链表法

基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。 第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。

邻接链表的存储结构

链表中的结点称为表结点，每个结点由三个域组成，其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号)，链域(nextarc)指向下一个与顶点Vi邻接的表结点，数据域(info)存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。

每个链表设一个表头结点(称为顶点结点)，由两个域组成，链域(firstarc)指向链表中的第一个结点，数据域(data) 存储顶点名或其他信息。

在图的邻接链表表示中，所有顶点结点用一个向量 以顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为表头向量，向量的下标指示顶点的序号。 用邻接链表存储图时，对无向图，其邻接链表是唯一的，对有向图，其邻接链表有两种形式：正邻接链表（出度直观）；逆邻接链表（入度直观）。

#define MAX_VEX  30     /*  最大顶点数  */
typedef int  InfoType;
typedef enum { DG, AG, WDG,WAG } GraphKind ;
typedef struct LinkNode
{  int  adjvex ;        // 邻接点在头结点数组中的位置(下标)
   InfoType    info  ;       // 与边或弧相关的信息, 如权值
   struct LinkNode  *nextarc ;     // 指向下一个表结点
} LinkNode ;    /*  表结点类型定义   */
typedef struct VexNode
{  VexType  data;     // 顶点信息
   int  indegree ;   //  顶点的度, 有向图是入度或出度或没有 
   LinkNode  *firstarc ;    // 指向第一个表结点
} VexNode ;     /*  顶点结点类型定义   */
typedef struct ArcType
{  VexType  vex1, vex2 ;    /*  弧或边所依附的两个顶点 */
   InfoType    info  ;       // 与边或弧相关的信息, 如权值
} ArcType ;     /*  弧或边的结构定义  */
typedef struct
{   GraphKind  kind ;       /*  图的种类标志   */
    int vexnum ;
    VexNode   AdjList[MAX_VEX] ;
} ALGraph ;     /*  图的结构定义   */

利用上述的存储结构描述，可方便地实现图的基本操作。

邻接表法的特点

• 表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目；
• 在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间；
• 在无向图，顶点Vi的度是第i个链表的结点数；
• 对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点Vi为出度(即为弧的起点)而建立的邻接表；逆邻接表是以顶点Vi为入度(即为弧的终点)而建立的邻接表；
• 在有向图中，第i个链表中的结点数是顶点Vi的出 (或入)度；求入 (或出)度，须遍历整个邻接表；
• 在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点；

十字链表法

十字链表(Orthogonal List)是有向图的另一种链式存储结构，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。

十字链表的存储结构

在这种结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将弧结点分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。 每个域的作用如下：

• data域：存储和顶点相关的信息；
• 指针域firstin：指向以该顶点为弧头的第一条弧所对应的弧结点；
• 指针域firstout：指向以该顶点为弧尾的第一条弧所对应的弧结点；
• 尾域tailvex：指示弧尾顶点在图中的位置；
• 头域headvex：指示弧头顶点在图中的位置；
• 指针域hlink：指向弧头相同的下一条弧；
• 指针域tlink：指向弧尾相同的下一条弧；
• Info域：指向该弧的相关信息；

#define INFINITY  MAX_VAL     /* 最大值∞ */
#define MAX_VEX  30     //  最大顶点数  
typedef struct ArcNode
{   int  tailvex , headvex ;   //  尾结点和头结点在图中的位置
    InfoType    info  ;       // 与弧相关的信息, 如权值
    struct ArcNode  *hlink , *tlink ; 
} ArcNode ;    /*  弧结点类型定义   */
typedef struct VexNode
{  VexType  data;     // 顶点信息
   ArcNode  *firstin , *firstout ;
} VexNode ;    /*  顶点结点类型定义   */
typedef struct
{  int vexnum ;
   VexNode  xlist[MAX_VEX] ;
} OLGraph ;   /*  图的类型定义   */

十字链表法的特点

从这种存储结构图可以看出，从一个顶点结点的firstout出发，沿表结点的tlink指针构成了正邻接表的链表结构，而从一个顶点结点的firstin出发，沿表结点的hlink指针构成了逆邻接表的链表结构。

邻接多重表

邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构。 邻接表是无向图的一种有效的存储结构，在无向图的邻接表中，一条边(v,w)的两个表结点分别初选在以v和w为头结点的链表中，很容易求得顶点和边的信息，但在涉及到边的操作会带来不便。

邻接多重表的存储结构

邻接多重表的结构和十字链表类似，每条边用一个结点表示；邻接多重表中的顶点结点结构与邻接表中的完全相同，而表结点包括六个域：

• Data域：存储和顶点相关的信息；
• 指针域firstedge：指向依附于该顶点的第一条边所对应的表结点；
• 标志域mark：用以标识该条边是否被访问过；
• ivex和jvex域：分别保存该边所依附的两个顶点在图中的位置；
• info域：保存该边的相关信息；
• 指针域ilink：指向下一条依附于顶点ivex的边；
• 指针域jlink：指向下一条依附于顶点jvex的边；

#define INFINITY  MAX_VAL     /* 最大值∞ */
#define MAX_VEX  30     /*  最大顶点数  */
typedef  emnu { unvisited , visited }  Visitting ;
typedef struct EdgeNode
{  Visitting  mark ;    // 访问标记
   int  ivex , jvex  ;   // 该边依附的两个结点在图中的位置
   InfoType    info  ;       // 与边相关的信息, 如权值
struct EdgeNode  *ilink , *jlink ; 
// 分别指向依附于这两个顶点的下一条边
} EdgeNode ;    /*  弧边结点类型定义   */
typedef struct VexNode
{  VexType  data;     // 顶点信息
   ArcNode  *firsedge ;   //  指向依附于该顶点的第一条边
} VexNode ;    /*  顶点结点类型定义   */
typedef struct
{  int vexnum ;
   VexNode mullist[MAX_VEX] ;
} AMGraph ;

邻接多重表与邻接表的区别

邻接表的同一条边用两个表结点表示，而邻接多重表只用一个表结点表示；除标志域外，邻接多重表与邻接表表达的信息是相同的，因此，操作的实现也基本相似。

图的边表

在某些应用中，有时主要考察图中各个边的权值以及所依附的两个顶点，即图的结构主要由边来表示，称为边表存储结构。

图的边表的存储结构

在边表结构中，边采用顺序存储，每个边元素由三部分组成：边所依附的两个顶点和边的权值；图的顶点用另一个顺序结构的顶点表存储。

#define INFINITY  MAX_VAL     /* 最大值∞ */
#define MAX_VEX  30     /*  最大顶点数  */
#define MAX_EDGE  100     /*  最大边数  */
typedef struct ENode
{  int  ivex , jvex  ;   /*   边所依附的两个顶点  */
   WeightType    weight  ;       /*   边的权值   */
} ENode ;    /*  边表元素类型定义   */
typedef struct 
{  int  vexnum , edgenum ;     /*   顶点数和边数    */
   VexType  vexlist[MAX_VEX] ;    /*   顶点表    */
   ENode  edgelist[MAX_EDGE] ;     /*   边表    */ 
} ELGraph ;    

总结

图的存储结构依据图具体的应用会有不同的表现形式，有时候在一个问题的解决方案中需要用到的不止一种存储结构，熟练掌握图的数据结构是有效实现图算法的基础。

总结自：《数据结构（C语言版）》 清华大学出版社 严蔚敏、吴伟民编著