introduction-to-algorithms-learning-chapter11.md

title	date	tags	author	comments
算法导论研读与分析（十一）	2013-09-23 03:00:00 -0700	数据结构，图，存储	maclaon	false

图

图是重要的数据结构，在现实世界中有很多的应用，比如说网络，物流等，其相关算法在实际应用中有很大的用处。

分类

• 无向图 对于一个图，若每条边都是没有方向的，则称该图为无向图。图中与特定顶点相连的边数称为度，图示如下：

• 有向图 对于一个图G，若每条边都是有方向的，则称该图为有向图。图示如下。

• 无向完全图 具有n(n-1)/2条边的无向图称为无向完全图。

• 有向完全图 将具有n(n-1)条边的有向图。其度为出度和入度。

• 连通图 图$$G$$中任意两个顶点$$V_i$$和$$V_j$$都连通，则称为连通图。

• 强连通图（有向图） 在一个强连通图中，任意两个点都通过一定路径互相连通。

上图1是强连通图，而图2不是，因为没有一条路使得点4到达点1、2或3。

• 网 带”权值”的连通图称为网。如图所示:

存储

图的存储主要是维护途中每个接电之间的关系，其中链表和矩阵是常用的方式。

邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。设图$$G$$有$$n$$个顶点，则邻接矩阵是一个$$n*n$$的方阵，定义为：

$$$$

其示例图为:

从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足$$a_{ij} = a_{ji}$$。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。从矩阵中可以获得图的以下信息：

• 判断任意两顶点是否有边无边
• 知道某个顶点的度，其实就是这个顶点$$v_i$$在邻接矩阵中第i行或（第i列）的元素之和
• 顶点$$v_i$$的所有邻接点就是将矩阵中第i行元素扫描一遍

有向图和其邻接矩阵的存储方式:

邻接表

邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。邻接表的处理方法是这样的：

• 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。
• 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

其无向图的邻接表的结构示例图如下:

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。

十字链表

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。

只针对有向图，适用于计算出度和入度；