图解图的存储结构

刚开始接触图形结构的时候，觉得它很烧脑子，因为像线性表它仅有线性关系，树形结构有清晰度的层次结构，但是对于图形结构来说集合中的每一个元素都有可能有关系。所以在刚接触图形结构的时候，对于如何实现图形结构往往感到很困惑,后来发现我们其实只要弄清楚了图的存储结构那么用代码实现起来并不困难。

要清楚地理解图的存储结构，首先要明白图的存储结构里要存储些什么东西。要存储图形结构的信息，无非就是存储图的顶点（vector）和图的边（edge）。

下面给出两张图，以此来介绍图型结构的四种存储结构。注意（无向图和有向图的存储结构是有区别的，应当体会其中的区别）
G1（有向图）

如图所示G1有四个顶点（Vector）,四条有向边（Edge）

G2(无向图)

G2有五个顶点，六条边。

一，数组存储

数组表示法，应当是图的存储结构中最简单的，利用两个数组分别存储顶点（vector）和边（edge）。
1、我们先只考虑图顶点（vector）的信息：先利用一个数组把图顶点存储起来。
对于G1,它的顶点用数组存储：

对于G2，它的顶点用数组存储：

2、再来考虑图的边（edge），因为一条边连接两个顶点，为了描述这个关系，再利用一个二维数组来存储图的边。把二维数组看做一个矩阵。
对于有向图G1，它的边用二维数组存储：

其中E[i][j]为1表示，从顶点v[i]到顶点v[j]有边（这是有方向的）。

对于无向图G2,它的边也可以用二维数组来表示：

其中E[i][j]为1表示顶点V[i]与V[j]之间有边（没有方向），注意：这和有向图是不一样的，大家可以看到无向图的二维数组是关于对角线对称的。

这样通过一维数组来保存顶点数据信息，二维数组来表示两两顶点之间的边。就完成了对图形数据结构的存储。下面的三种方法其实也是利用数组和链表来对图形数据结构的存储。

二，邻接表存储

1、我们依旧先利用一维数组将图的顶点存储起来。
对于：G1

先强调一下弧头和弧尾以及弧的概念
弧头和弧尾都是指顶点，在G1中，对于Ea来说V1是弧头，V2是弧尾

2、再将图的边加进来，至于怎么加？如图所示：

看看是不是很简单？

其实就利用一个一维数组存储链表。链表的头结点是顶点（V_i），对于有向图头结点后面跟着的是以顶点（V_i）为弧头的弧。
对于无向图头结点后面跟着的是以顶点（V_i）弧（不分方向）
。

头结点：
头结点中有两个域 如图：

1，data域：存储顶点（V_i）的数据信息。
2，firstarc域：顾名思义就是该域指向与顶点（V_i）相连的第一条弧（arc）,这里指的第一条并没有特定的顺序，只是为了和之后的弧进行区分而出现的概念。

边节点（表节点，弧节点）
表节点中有三个域如图,

对于跟在头结点后面的表节点来说，它都对应着头结点中的顶点（V_i），且如果是有向图的边那么顶点（V_i）只能是边的弧头，对于无向图来说则没有要求。
1，adjvex:指示通过该边，与顶点（V_i）连接的另一个顶点在图中的位置，这里的位置可以用头结点在数组中的位置（下标）来表示。
2，next:指向与顶点（V_i）连接的下一条弧（该弧以顶点（V_i）为弧头）。
3，info：这是一个可以用来存储边的权值的域，文章中的都没有权值，所以不画出info域。
刚刚说过对于无向图和有向图应当注意它们的区别，用邻接表存储图形结构的时候，无向图的度就是链表中表节点的个数，如图无向图的邻接链表表示：

但是对于有向图，链表中表节点的个数是顶点（V_i）的出度，因为以（V_i）顶点为头结点的链表后面接着的表节点中是以顶点（V_i）为弧头的弧，所以要有向图的度还要求出有向图的入度，邻接表中的adjvex域值为i的表节点的个数是顶点（V_i）的入度。
为了方便求有向图的入度我们引入了逆邻接表，
G1逆邻接表如图：

在逆邻接表中，链表的头结点是顶点（V_i），对于有向图后面跟着的是以顶点（V_i）为弧尾的弧。
对比一下邻接表和逆邻接表

邻接表的头结点和逆接表的头结点，边节点一致，只不过是连接方式不一样。

邻接表：链表的头结点存储的（V_i）是弧头，后面跟着表节点中存储的是弧头（V_i）的弧。

简单来说链表中的表节点是头结点顶点（V_i）指出去的弧，所以链表中的表节点个数就是顶点（V

三，十字链表法

所谓的十字链表法就是结合了邻接表和逆邻接表，以方便求出图形结构的出度和入度。
我们来分析一下十字链表法中链表的节点。
头结点：头结点中有三个域如图所示：

信息域data：存储顶点（V_i）数据信息
指针域firstin：存储第一个以顶点（V_i）为弧头的边节点地址
指针域firstout：存储第一个顶点（V_i）为弧尾的边节点地址。

表节点（边节点）：有五个域，如图所示：

其中头域headvex和尾域tailvex顾名思义存储的是该边（弧）的弧头和弧尾的信息，可以是弧头和弧尾在数组中的位置。
链域hlink存储的是和该边弧头一样的边位置，即hlink指向和该边弧头一样的边。
链域tlink存储的是和该边弧尾一样的边位置，即hlink指向和该边弧尾一样的边。
信息域info中可以存储边的信息如权值。
下面给出图进行分析（图太难画了，我上传教材上的图进行分析）

四，邻接多重表

邻接多重表是针对于无向图改进的存储结构，因为利用方法二邻接表来存储无向图的时候，我们会发现无向图的一条边会出现在数组中两条不同的链表中，比如：

Ea出现在a[0]顶点后面，又出现在a[1]顶点后面。
这对我们对边进行操作的时候十分不便，假设我要删除一条边，那么我要在两条链表中去删除这条边两次，这增加了我们程序的复杂度。
邻接多重链表就是针对于无向图改进的存储结构，让一条边仅仅用一个节点表示。
一条边由一个节点六个域表示：如图所示：

mark域：用来标记这条边是否被检索过。
ivex和jvex域：这两个域中存储的是顶点的位置,因为一条边连接两个顶点，所以这两个域放在一起讲，ivex域中存储节点V_i的位置，jvex域中存储节点V_j的位置。
ilink和jlink域：这两个域中存放的是边的位置，那为什么一个边节点里面会存储两条边的位置呢？这是因为一条边对应两个顶点，而顶点的边都是由一个个边节点链接起来的，ilink中存储顶点V_i的下一条边的位置。
jlink中存储顶点V_j的下一条边的位置。
info域：可以用来存储边的权值。
头结点如图所示：

给出教材中利用多重链表对无向图G2的存储

我们可以看到其实不管是比较复杂的树形结构还是图形结构都可以用线性表来表示，想起了我们老师说过的数据结构其实只有两种，线性表的顺序结构，和线性表的链式结构。虽然不敢说老师的话是真理，但是确实有他的道理，像栈，队列，树和图都可以用线性表来表示。有点万变不离其中的意思。

参考教材：《数据结构》（严蔚敏 吴伟民）
《数据结构与算法》（传智播客）