图——图的基础

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语言描述如下：

   

#define INFINITY 10000		/*定义一个无限大的值*/
#define MaxSize 50			/*最大顶点个数*/
typedef enum{DG,DN,UG,UN}GraphKind; 	/*图的类型：有向图、有向网、无向图和无向网*/
typedef struct
{
	VRType adj;			/*对于无权图，用1表示相邻，0表示不相邻；对于带权图，存储权值*/
	InfoPtr *info; 			/*与弧或边的相关信息*/
}ArcNode,AdjMatrix[MaxSize][MaxSize];
typedef struct				/*图的类型定义*/
{
	VertexType vex[MaxSize]; 	/*用于存储顶点*/
	AdjMatrix arc; 				/*邻接矩阵，存储边或弧的信息*/
	int vexnum,arcnum; 			/*顶点数和边（弧）的数目*/
	GraphKind kind; 			/*图的类型*/
}MGraph;

 

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

 （2）邻接表表示法

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

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

#define MaxSize 50			/*最大顶点个数*/
typedef enum{DG,DN,UG,UN}GraphKind; 	/*图的类型：有向图、有向网、无向图和无向网*/
typedef struct ArcNode		/*边结点的类型定义*/
{
	int adjvex; 			/*弧指向的顶点的位置*/
	InfoPtr *info;			/*与弧相关的信息*/
	struct ArcNode *nextarc; 	/*指示下一个与该顶点相邻接的顶点*/
}ArcNode;
typedef struct VNode		/*头结点的类型定义*/
{
	VertexType data; 		/*用于存储顶点*/
	ArcNode *firstarc; 		/*指示第一个与该顶点邻接的顶点*/
}VNode,AdjList[MaxSize];
typedef struct				/*图的类型定义*/
{
	AdjList vertex;
	int vexnum,arcnum;		/*图的顶点数目与弧的数目*/
	GraphKind kind; 		/*图的类型*/
}AdjGraph;

 

（3）十字链表表示法（有向图）

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

 

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

#define MaxSize 50				/*最大顶点个数*/
typedef struct ArcNode			/*弧结点的类型定义*/
{
    int headvex,tailvex; 			/*弧的头顶点和尾顶点位置*/
    InfoPtr *info;				/*与弧相关的信息*/
    struct *hlink,*tlink; 			/*指示弧头和弧尾相同的结点*/
}ArcNode;
typedef struct VNode			/*顶点结点的类型定义*/
{
    VertexType data; 			/*用于存储顶点*/
    ArcNode *firstin,*firstout; 		/*分别指向顶点的第一条入弧和出弧*/
}VNode;
typedef struct					/*图的类型定义*/
{
    VNode vertex[MaxSize];
    int vexnum,arcnum;		/*图的顶点数目与弧的数目*/
}OLGraph;

 

（4）邻接多重链表表示法（无向图）

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

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

#define MaxSize 50				/*最大顶点个数*/
typedef struct EdgeNode			/*边结点的类型定义*/
{
    int mark,ivex,jvex; 			/*访问标志和边的两个顶点位置*/
    InfoPtr *info;				/*与边相关的信息*/
    struct *ilink,*jlink; 			/*指示与边顶点相同的结点*/
}EdgeNode;
typedef struct VNode			/*顶点结点的类型定义*/
{
    VertexType data; 			/*用于存储顶点*/
    EdgeNode *firstedge; 		/*指向依附于顶点的第一条边*/
}VexNode;
typedef struct					/*图的类型定义*/
{
    VexNode vertex[MaxSize];
    int vexnum,edgenum;		/*图的顶点数目与边的数目*/
}AdjMultiGraph;