假期连载之十三
（图—图的基本概念、ADT、存储结构表示）
图graph部分涉及到了许多离散数学方面的理论知识，因此本节需要读者具备一定的离散数学背景—当然，重要的概念和性质我们会附带说明。图是一种更为灵活复杂的非线性结构，理论上讲它比树的实用性更强，但算法设计的复杂度上也存在很大提升。图最典型的应用领域有电路分析、寻找最短路线、项目规划、鉴别化合物、统计力学、遗传学、控制论、语言学以及一些社会科学。
图的基本概念
图是一种网状数据结构，其形式定义如下：
Graph=(V,R);
V={x|x属于DataObject};
R={VR};
VR={<x,y>|P(x,y)交(x,y属于V)};
其中DataObject是一个数据集合，其中所有的元素都具有相同的特性。V中的数据元素通常称为顶点Vertex，VR是两个顶点之间的关系的集合，P(x,y)表示x和y之间有特定的关联属性P。
若有VR内的元素<x,y>，则其表示从顶点x到顶点y的一条弧Arc，并称x为弧尾Tail或起始点，称y为弧头Head或终端点，此时图中的边是有方向的，称这样的图为有向图。
若有VR内的元素<x,y>，必有<y,x>，即VR是对称关系，这时用无序对的表示方法来代替两个有序对(x,y)，表示x和y之间的一条边，此时的图称为无向图。
设n表示图中的顶点个数，用e表示图中边或弧的数目，且不考虑图中每个顶点到其自身的边或弧。对于无向图而言，如果e=n(n-1)/2，则称其为无向完全图，对应的有向图被称为有向完全图。对于e<nlogn的图称为稀疏图，否则称稠密图。
子图是指一个图的顶点结构和关联不发生改变，只存在其中一部分的图。在无向图G=(V,{E})中，如果边(v1,v2)属于E，则称v1、v2互为邻接点，并且边(v1,v2)依附于顶点v1、v2，或者说边与v1、v2相关联。而对于有向图而言，如果存在弧<v1,v2>属于A，则称顶点v1邻接到顶点v2，顶点v2邻接自顶点v1，或者说弧<v1,v2>与顶点v1、v2相关联。
度是指与顶点v关联的边数，记作deg(v)。在有向图中顶点为弧头则称其为入度ID(v)，为弧尾则称其为出度OD(v)，顶点的入度的数目必然和出度相等。
在实际应用中，往往赋给边或弧一定的数值，成为权。这种带权信息的图被称为赋权图或网。
路径是指任意两个顶点之间沿边或弧方向的顶点序列。如果G是有向图，则其路径也是有向的。在一个路径中，如果第一个顶点和最后一个顶点相同，则称该路径为一个回路或环。若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。除第一个和最后一个顶点外，其余个顶点均不重复出现的回路称为简单回路。
在无向图G中，如果从vi到vj有路径相通，则称其是连通的。如果对于任意两个顶点均是连通的，则图被称为连通图。无向图的极大连通子图被称为无向图的连通分量。而对有向图而言，如果对于每对顶点，都有互相连通的路径，则称其为强连通图，它的极大连通子图被称为强连通分量。
现在给出图的抽象数据类型定义：
ADT Graph
{
数据对象V:一个集合，集合中所有元素有相同的特性
数据关系R:R={VR};
基本操作:
CreateGraph(G); //创建图G
DestoryGraph(G); //销毁图G
LocateVertex(G,v); //若存在顶点v，则返回v的位置，否则返回NULL
GetVertex(G,i); //返回G中顶点v的第i个顶点的值
FirstAdjVertex(G,v); //返回G中顶点v的第i个邻接点的值
NextAdjVertex(G,v,w); //返回返回G中顶点v的下一个(w个后面)邻接点的值，如果w为最后一个邻接点，则返回NULL
InsertVertex(G,u); //添加一个点u
DeleteVertex(G,v); //删除图中的顶点v以及相关联的弧
InsertArc(G,v,w); //向图中添加一条从v指向w的弧
DeleteArc(G,v,w); //删除图中从v指向w的弧
TraverseGraph(G); //遍历图G
}
图的基本存储结构
现在，我们按照图的性质，介绍四种常用的存储表示法。大体上来说依然为顺序存储和链式存储两种类型。
1、 图的邻接矩阵表示
邻接矩阵adjacency matrix表示法实际上就是数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。
在储存关联关系的二维数组中，1代表了无权图中两顶点间路径连通，0则反之，其阶为顶点个数。
邻接矩阵表示的特点如下：
a)存储空间方面，对无向图而言，其邻接矩阵为对称矩阵，因而可采用相关的压缩存储法。但对于有向图而言，由于顶点间不一定互相连通，因此需要n^2个存储空间。
b)便于计算，由于采用了数组表示，关于图中顶点的基本运算就相对简便。综合而言，邻接矩阵不适合存储稀疏图。
2、邻接表表示法
邻接表adjacency matrix吸取了邻接矩阵的优点，同时凭借链式结构的特点对上述方法做出改进，在节省存储空间上起到了很大作用。邻接表对图中每个顶点建立一个带头结点的边链表。
表头结点有两部分构成：数据域vexdata以及链域firstarc，用于指向链表中第一个顶点。对于边表，由表示图中顶点间邻接关系的n个边链表构成。因而结点在包括了上述两个结点域之外，还附带一个邻接点域adjvex，用于存放与该点相邻的顶点在图中的位置。
邻接表虽然进一步节省了存储空间，但在一些基本运算过程中，例如求某个顶点的入度，则必须遍历整个邻接表，在时间复杂度上并不如邻接矩阵优异。
为了解决一些计算上的问题，还可以另外设置一个逆邻接表，就可以满足一些常用运算的需要。
3、正交链表（十字链表）
正交链表Orthogonal Lists是有向图的另一种存储结构，它在邻接表表示法所不擅长的有向图运算领域做到了很好的效果。其实质是将邻接表和逆邻接表结合起来形成的一种链表。
正交链表的弧结点结构包括了tailvex弧尾顶点位置、headvex弧头顶点位置、hlink指向与此弧的弧头相同的下一条弧、tlink指向与此弧的弧尾相同的下一条弧、info该弧的相关信息。
其顶点结点包括了data数据域、firstin指向该顶点作为弧头的第一个弧结点、firstout指向该顶点作为弧尾的第一个弧结点。
4、 邻接多重表
邻接多重表Adjacency Multi_list是无向图的另外一种存储结构。这种结构相较于邻接表来说结构复杂，运算算法难度较高，但在处理无向图的边信息时却大大节省了算法时间，是一种高效的无向图存储表示。
其边结点的结构包括了mark标记该条边是否已被搜索、ivex/jvex为该边依附的两个顶点在图中的位置、ilink指向下一条依附于顶点ivex的边、jlink指向下一条依附于顶点jvex的边、info边信息。
顶点结点结构包括了data数据域、firstedge指向第一条依附于该顶点的边。
以上四种存储策略分别适用于不同的需求环境，具体应采取何种存储结构应按照实际情况而定。为统一起见今后我们涉及到图的基本运算时，一般以邻接矩阵和邻接表这两个基本结构为例。
(未完待续)