【数据结构】图的存储

邻接矩阵

表示方法

代码定义

结构特点与度的信息

邻接表

表示方法

代码定义

结构特点与度的信息

十字链表

表示方法

第二步，将顶点x的firstIn域与所有headvex域为x的弧连起来。

结构特点与度的信息

邻接多重表

表示方法

结构特点与度的信息

图的存储方式辨析

邻接矩阵

表示方法

邻接矩阵是指通过一个一维数组来存放图里各个顶点的相关信息，再借助一个二维数组来存放图中边的信息，用于存储顶点邻接关系的二维数组被称作邻接矩阵。

邻接矩阵的命名规则如下：

对于无权图，若两点i,j有边相连，则A[i][j]=1；若没有边相连，则A[i][j]=0或无穷。

对于有权图，若两点i,j有边相连，则A[i][j]=边的权重；若没有边相连，则A[i][j]=0或无穷。

对于有向图，若有从i出发到j的箭头（i为弧尾，j为弧头），则A[i][j]=1或边的权重（无权或有权）。

给出三个例子，体会邻接矩阵：

例一：

其邻接矩阵为：

	1	2	3	4	5
1	0	1	0	1	0
2	1	0	1	0	0
3	0	1	0	1	1
4	1	0	1	0	0
5	0	0	1	0	0

例二：

其邻接矩阵为：

	1	2	3	4
1	0	1	1	0
2	0	0	0	0
3	0	0	0	1
4	1	0	0	0

例三：

其邻接矩阵为：

	1	2	3	4	5
1	0	2	0	10	0
2	2	0	7	0	0
3	0	7	0	5	8
4	10	0	5	0	0
5	0	0	8	0	0

代码定义

易知邻接矩阵的构成要素应该包括顶点表顶点数、边表边数，具体代码如下：

#define MaxVertexnum 100                 //最大顶点数
typedef char VertexType;                 //顶点数据类型
typedef int EdgeType;                    //边数据类型
typedef struct {                                    //邻接矩阵定义VextexType vex[MaxVertexnum];                   //顶点表EdgeType edge[MaxVertexnum][MaxVertexnum];      //边表int vexnum arcnum;                        //顶点数与边数
}MGraph;

结构特点与度的信息

邻接矩阵有下面几个特性：

1、无向图的邻接矩阵必为对称矩阵，所以存储时可以考虑压缩存储（【数据结构】矩阵与数组）。

2、有向图的邻接矩阵若为三角矩阵，则结构无环，一定可以进行拓扑排序（过两天出拓扑排序）。
3、邻接矩阵适合存储稠密图。

那么从邻接矩阵中如何得到度的信息呢？

对于无权图，若为无向图的邻接矩阵，则顶点i的度为第i行所有元素的和；若为有向图的邻接矩阵，则 $\sum_{k}^{n}a_{i,k}$ (第i行所有元素的和)表示顶点i的出度， $\sum_{k}^{n}a_{k,i}$ (第i列所有元素的和)表示顶点i的入度。

这里有一个小的知识点，对于无权图G邻接矩阵A的n次幂，有下面的结论：

$A^{n}[i][j]$ 表示路径长度为n的从i到j的路径条数。

如何证明？

考察矩阵的乘法，可知 $A^{2}[i][j]=\sum_{k}^{n}A[i][k]*A[k][j]$ 。由于无权图的邻接矩阵只有0或1，所以对于求和符号里的单次相乘，如果i到k与k到j都有路径，则相乘得出的结果为1；若至少一条路径为0，则相乘结果为0；求和就是把所有的1加起来，即从i出发经过1-n所有顶点然后到j的路径条数。

考虑累乘的意义，n次幂代表着路径长度为n。（如果不清楚可以拿三次方自己手算一下，就很明了了）。

邻接表

表示方法

邻接表为图G中的每个顶点建立一个单链表，对于无向图，第i个单链表中的结点表示与顶点i相连的边；对于有向图，则表示以顶点i为起点的弧（即有向边）。每个顶点对应的单链表称为该顶点的边表（在有向图中称为出边表）。这些边表的头指针以及顶点的数据信息采用顺序存储的方式，共同构成顶点表。

因此，在邻接表结构中包含两种结点：顶点表结点和边表结点。

顶点表节点与边表节点结构示意如下所示：

对于下面的图，其邻接表示意如下：

例一：

例二：

代码定义

邻接表的代码结构包括了顶点表、边表和包含这两者以及其他信息的整个图结构，具体定义如下：

#define MaxVertexNum 100                //顶点数typedef struct ANode{            //边表节点int adjvex;                  //这里因为顶点数据用数组存储，可以用数组下标int型表示而不用charstruct ANode *nextarc;       //指针域
}ANode;typedef struct VNode{         //顶点节点和顶点表char data;                    //顶点数据域ANode *firstarc;              //第一个指针
}VNode,AdList[MaxVertexNum];typedef struct{AdList vertices;            //顶点表int vexnum, arcnum;         //边点数量
}ALGraph;

结构特点与度的信息

邻接表的结构特点如下：

1、无向图的边表结点数是总结点数的两倍，有向图的边表结点数与总结点数相等。无向图邻接表存储空间为O( $\left | V \right |+2\left | E \right |$ )，有向图邻接表存储空间为O( $\left | V \right |+\left | E \right |$ )。

2、邻接表不唯一，因为边表结点链表的次序可以改变。

3、邻接表适合存储稀疏图。

邻接表隐含的度的信息如下：

1、无向图顶点表某个顶点连着的边表结点个数就是该顶点的度。

2、有向图定顶点的出度等于该顶点连着的边表结点个数，入度需要遍历整个邻接表进行统计。

十字链表

表示方法

十字链表用于表示有向图。十字链表有两种结点结构，一种为顶点结点，一种为弧结点。

顶点结点包含三个域：数据域data、第一个入度域firstin（以该点为弧头的第一个弧）和第一个出度域firstout（以该点为弧尾的第一个弧）。

弧结点包含五个域：弧尾数据域tailvex、弧头数据域headvex、相同弧头指针域hlink（即与该弧同弧头的下一个弧）、相同弧尾指针域tlink（即与该弧同弧尾的下一个弧）和权值域info。

结构示意图如下：

这里注意不要轻易改变域的顺序，就按照上图原封不动地抄下来。

那么为什么要这样设定呢？现在给出一个无权图（无info域）的十字链表构建过程就能很清晰地知道了。

第一步，列出顶点表，并将所有以该顶点为弧尾（从该点出发）的弧列在该顶点的同一行，并且把同一行的弧都连起来。

第二步，将顶点x的firstIn域与所有headvex域为x的弧连起来。

那么一个图的十字链表就画完了。

结构特点与度的信息

从上面的绘图过程可以看出，十字链表表示的图很轻松就能够找到一个顶点的入度、出度或者一个弧相邻的两个点。同时，删除一个节点、一个弧的时间复杂度也是很低的。

需要注意的是，十字链表不唯一，但十字链表唯一确定一个图。

邻接多重表

表示方法

与十字链表相对应，无向图可以用类似的方法表示。但是由于无向图边的无向性，我们不用区分头和尾。

邻接多重表链表有两种结点结构，一种为顶点结点，一种为弧结点。

顶点结点包含两个域：数据域data、第一条边域firsedge。

弧结点包含五个域：i顶点数据域ivex、i顶点相邻边指针域ilink、j顶点数据域jvex、j顶点相邻边指针域jlink和权值域info。

这里同样给一个无向无权图的构建过程。

第一步，列出顶点表与所有边。

第二步，哪里有空插哪里。

结构特点与度的信息

相似地，邻接多重表表示的图很轻松就能够找到一个顶点的度或者一个边相邻的两个点。同时，删除一个节点、一个弧的时间复杂度也是很低的。

图的存储方式辨析

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	$O(\left \| V^{2} \right \|)$	$O(\left \| V \right \|+\left \| E \right \|)$ 或 $O(\left \| V \right \|+2\left \| E \right \|)$	$O(\left \| V \right \|+\left \| E \right \|)$	$O(\left \| V \right \|+\left \| E \right \|)$
找邻边	时间复杂度O(V)	有向图的入度要遍历整个表，别的挺方便	方便	方便
删除边或者顶点	删边容易删点难	有向：删边容易删点难；无向：都难	方便	方便
适用于	稠密	稀疏	只能有向	只能无向
表示方式	唯一	不唯一	不唯一	不唯一