图的存储结构-大学计算机基础　

由于图的结构比较复杂，任意两个顶点之间都可能存在关系，因此用简单的顺序存储来表示图是不可能，而若使用多重链表的方式（即一个数据域多个指针域的节点来表示），这将会出现严重的空间浪费或操作不便。这里总结一下常用的表示图的方法。

1.邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称邻接矩阵）存储图中的边或弧的信息，如图9-33所示。

图9-33　无向图的邻接矩阵存储

无向图由于边不区分方向，所以其邻接矩阵是一个对称矩阵。邻接矩阵中的0表示边不存在，主对角线全为0表示图中不存在自环。

带权有向图的邻接矩阵，如图9-34所示：

图9-34　带权有向图的邻接矩阵存储

在带权有向图的邻接矩阵中，数字表示权值weight，「无穷」表示弧不存在。由于权值可能为0，所以不能像在无向图的邻接矩阵中那样使用0来表示弧不存在。

优缺点：

·优点：结构简单，操作方便；

·缺点：对于稀疏图，这种实现方式将浪费大量的空间。

2.邻接表

邻接表是一种将数组与链表相结合的存储方法。其具体实现为：将图中顶点用一个一维数组存储，每个顶点Vi的所有邻接点用一个单链表来存储。这种方式和树结构中孩子表示法一样。

对于有向图其邻接表结构，如图9-35所示：(www.xing528.com)

图9-35　有向图的邻接表结构

有向图的邻接表是以顶点为弧尾来存储边表的，这样很容易求一个顶点的出度（顶点对应单链表的长度），但若求一个顶点的入度，则需遍历整个图才行。这时可以建立一个有向图的逆邻接表即对每个顶点v都建立一个弧头尾v的单链表。如上图所示。

本算法的时间复杂度为O（N+E），其中N、E分别为顶点数和边数，邻接表实现比较适合表示稀疏图。

3.十字链表

十字链表（Orthogonal List）是将邻接表和逆邻接表相结合的存储方法，它解决了邻接表（或逆邻接表）的缺陷，即求入度（或出度）时必须遍历整个图。

十字链表的结构如9-36所示：

图9-36　有向图的十字链表结构

图中：

·firstIn表示入边表（即是逆邻接表中的单链表）头指针，firstOut表示出边表（即是邻接表中的单链表）头指针，data表示顶点数据。

·tailVex表示边的起点在顶点数组中的下标，tailNext值出边表指针域，指向起点相同的下一条边。

·head Vex表示边的终点在顶点数组中的下标，headNext指入边表指针域，指向终点相同的下一条边。

十字链表创建图算法的时间复杂度和邻接表相同都为O（N+E）。在有图的应用中推荐使用。