邻接矩阵和邻接表

邻接表和邻接矩阵

                                             ——图的两种存储结构

邻接矩阵

用二维数组表示：

如下图所示，图中有1指向2，1指向3，3指向4，4指向1共四种情况。

故在矩阵中，[1][2]，[1][3]，[3][4]，[4][1]四个位置被标记上了1，而其余为0的地方则表示没有指向关系。

注意点：

1.由这种标记方式可以看出，对于无向图来说，（a，b）和（b，a）属于同一条边，故在矩阵中[a][b]，[b][a]都会被标记上，所以无向图的邻接矩阵是关于主对角线的对称矩阵，而有向图的邻接矩阵一般不具有对称性；

2.对于无向图来说，顶点i的度=邻接矩阵第i行的元素的和；

   对于有向图来说，顶点i的入度=第i列元素的和，顶点i的出度=第i行元素的和；

3.用0,1标记大多只针对无权图，如果为有权图的话标记的为权值；

 

缺点：

一般图的边比较少，且邻接矩阵的非零元素比较少，属于稀疏矩阵，所以很大程度上会造成空间的浪费。

 

 

邻接表

它是图的链式存储结构：

1.为每一个顶点建立一个单链表；

2.第i个单链表中包含顶点Vi的所有邻接顶点；

表示法：

1.头结点：

 

Date（数据域：存放顶点Vi的信息）

Firstarc（链域：指向单链表的第一个结点）

2.表结点：

Adjvex （邻接点域：表Vi邻接点的位置）

Nextarc （链域：指向下一个边或弧的结点）

Info、 （数据域：如权值）

3.每个单链表都设有一个头结点；

4.每个单链表的头结点另外用顺序存储结构存储。

 

 

注意：

1.第i条链表上的节点数为Vi的出度（求出度容易，求入度难，求入度用逆邻接表）；

2.邻接表是不唯一的，因为各个边结点的入链的顺序是任意的；

3.邻接表形成之后，形成的图却是唯一的；