数据结构-图-存储结构

原文链接

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。而多重链表的方式，要么会造成很多存储单元的浪费，要么又带来操作的不便。因此，对于图来说，如何对它实现物理存储是个难题，接下来我们介绍五种不同的存储结构。

一、邻接矩阵

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

设图G有 n 个顶点，则邻接矩阵 A 是一个 n*n 的方阵，定义为： $$ A[i][j] = \begin{cases} 1，& 若(v_i,v_j)或<v_i,v_j> 是E(G)中的边 \ 0，& 若(v_i,v_j)或<v_i,v_j> 不是E(G)中的边 \end{cases} $$ 下图是一个无向图和它的邻接矩阵：

可以看出：

无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的)。因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
对于无向图，邻接矩阵的第 $i$ 行(或第 $i$ 列) 非零元素(或非 $\infty$ 元素)的个数正好是第 $i$ 个顶点的度 $TD(v_i)$。比如顶点 $v_1$ 的度就是 1+0+1+0=2。
求顶点 $v_i$的所有邻接点就是将矩阵中第 $i$ 行元素扫描一遍，$A[i][j]$ 为 1 就是邻接点。

下图是有向图和它的邻接矩阵：

可以看出：

主对角线上数值依然为 0 。但因为是有向图，所以此矩阵并不对称。
有向图讲究入度与出度，顶点 $v_1$ 的入度是 1 ，正好是第 $v_1$ 列各数之和。顶点 $v_1$ 的出度为 2，即第 $v_1$ 行的各数之和。
与无向图同样的办法，判断顶点 $v_i$ 到 $v_j$ 是否存在弧，只需要查找矩阵中 $A[i][j]$ 是否为 1 即可。

对于带权图而言，若顶点 $v_i$ 和 $v_j$ 之间有边相连，则邻接矩阵中对应项存放着该边对应的权值 $$ A[i][j] = \begin{cases} W_{ij}, & 若(v_i,v_j) \in E 或 <v_i,v_j> \in E \ 0, & 若 i=j \ \infty, & 反之 \end{cases} $$ 下图是有向网图和它的邻接矩阵：

通过以上对无向图、有向图和网的描述，可定义出邻接矩阵的存储结构：

1
2
3
4
5
6
7
8
#define MaxVertexNum 100 //顶点数目最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum]; //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
    int vexnum,arcnum; //图的当前顶点数和弧数
}MGraph;

注意:
在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点信息等均可忽略)。
当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType可定义为值为0和1的枚举类型。
无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。
邻接矩阵表示法的空间复杂度为 $O(n^2)$ ，其中 $n$ 为图的顶点数 $|V|$ 。
用邻接矩阵法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
稠密图适合使用邻接矩阵的存储表示。

二、邻接表

当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，如下图所示：

而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

所谓邻接表，是指对图 $G$ 中的每个顶点 $v_i$ 建立一个单链表，第 $i$ 个单链表中的结点表示依附于顶点 $v_i$ 的边(对于有向图则是以顶点 $v_i$ 为尾的弧)，这个单链表就称为顶点 $v_i$ 的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点：顶点表结点和边表结点，如下图所示：

顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc)构成，边表（邻接表）结点由邻接点域（adjvex) 和指向下一条邻接边的指针域（nextarc)构成。

无向图的邻接表的实例如下图所示。

有向图的邻接表的实例如下图所示。

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。

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

图的邻接表存储结构定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define MAXVEX 100 //图中顶点数目的最大值
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义

/*边表结点*/
typedef struct EdgeNode{
    int adjvex; //该弧所指向的顶点的下标或者位置
    EdgeType weight; //权值，对于非网图可以不需要
    struct EdgeNode *next; //指向下一个邻接点
}EdgeNode;

/*顶点表结点*/
typedef struct VertexNode{
    Vertex data; //顶点域，存储顶点信息
    EdgeNode *firstedge; //边表头指针
}vertexNode, AdjList[MAXVEX];

/*邻接表*/
typedef struct{
    AdjList adjList;
    int numVertexes,numEdges; //图中当前顶点数和边数
}

图的邻接表存储方法具有以下特点

若G为无向图，则所需的存储空间为 $O(|V|+2|E|)$ ;若G为有向图，则所需的存储空间为 O(|V|+|E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。
对于稀疏图，采用邻接表表示将极大地节省内存空间。
在邻接表中，给定一顶点，能很容易找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为 $O(n)$ 。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一个结点，效率较低。
在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

三、十字链表

十字链表是有向图的一种链式存储结构。

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。

有没有可能把邻接表与逆邻接表结合起来呢？答案是肯定的，就是把它们整合在一起。这就是我们现在要介绍的有向图的一种存储方法：十字链表（Orthogonal List）。

我们重新定义顶点表结点结构如下表所示：

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

重新定义的边表结点结构如下表所示。

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

接下来通过一个例子详细介绍十字链表的结构。

如下图所示，顶点依然是存入一个一维数组 ${V_0,V_1,V_2,V_3}$ ，实线箭头指针的图示完全与的邻接表的结构相同。就以顶点 $V_0$ 来说，firstout指向的是出边表中的第一个结点 $V_3$ 。所以 $V_0$ 边表结点的 $headvex=3$ ，而tailvex 就是当前顶点 $V_0$ 的下标，由于 $V_0$ 只有一个出边顶点，所以headlink 和 taillink都是空。

**我们重点需要来解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。**对于 $V_0$ 来说，它有两个顶点 $V_1$ 和 $V_2$ 的入边。因此 $V_0$ 的 firstin 指向顶点 $V_1$ 的边表结点中 $headvex$ 为 0 的结点，如上图右图中的 ①。接着由入边结点的 $headlink$ 指向下一个入边顶点 $V_2$,如图中的②。对于顶点 $V_1$ ，它有一个入边顶点 $V_2$ ，所以它的 firstin指向顶点 $V_2$ 的边表结点中 headvex 为1的节点，如图中的 ③。顶点 $V_2$ 和 $V_3$ 也是同样有一个入边顶点，如图中④和⑤。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到 $V_1$ 为尾的弧，也容易找到以 $V_1$ 为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此在有向图的应用中，十字链表是非常好的数据结构模型。

四、邻接多重表

邻接多重表是无向图的另一种链式存储结构。

在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。比如下图中，若要删除左图的 $(V_0,V_2)$ 这条边，需要对邻接表结构中右边表的阴影两个结点进行删除操作，显然这是比较繁琐的。

??? 这个图错了吧，阴影部分应该是 $V_0$ 邻接表第2个，$V_2$ 邻接表第一个

重新定义的边表结点结构如下表所示。

其中 ivex 和 jvex 是与某条边依附的两个顶点在顶点表中下标。ilink 指向依附顶点 ivex 的下一条边，jlink 指向依附顶点 jvex 的下一条边。这就是邻接多重表结构。

每个顶点也用一个结点表示，它由如下所示的两个域组成。

其中，data域存储该顶点的相关信息，firstedge域指示第一条依附于该顶点的边。

我们来看结构示意图的绘制过程，理解了它是如何连线的，也就理解邻接多重表构造原理了。如下图7所示，左图告诉我们它有 4 个顶点和 5条边，显然，我们就应该先将 4 个顶点和 5 条边的边表结点画出来。

我们开始连线，如图，首先连线的①②③④就是将顶点 firstedge 指向一条边，顶点下标要与 ivex 的值相同，这很好理解。接着，由于顶点 $V_0$ 的 $(V_0,V_1)$ 边的邻边有 $(V_0,V_3)$ 和 $(V_0,V_2)$ 。因此⑤⑥的连线就是满足指向下一条依附于顶点 $V_0$ 的边的目标，注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。 同样的道理，连线⑦就是指 $(V_1,V_0)$ 这条边，它是相当于顶点 $V_1$ 指向 $(V_1,V_2)$ 边后的下一条。$V_2$ 有三条边依附，所以在 ③之后就有了⑧⑨。连线④的就是顶点 $V_3$ 在连线 ④之后的下一条边。左图一共有 5 条边，所以右图有 10 条连线，完全符合预期。

到这里，可以明显的看出，邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了，若要删除左图的 $(V_0,V_2)$ 这条边，只需要将右图的 ⑥⑨的链接指向改为 NULL 即可。

五、边集数组

**边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成。**如下图所示，显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。

数据结构-图-存储结构#

一、邻接矩阵#

二、邻接表#

三、十字链表#

四、邻接多重表#

五、边集数组#