【数据结构】—— chapter 06 图的存储及基本操作 (part1)

6.2 图的存储及基本操作

6.2.1 邻接矩阵法

数组实现的顺序存储。用一维数组存顶点信息，二维数组存储图中边的信息（此二维数组称为邻接矩阵）。

1. 无向图、有向图对应的邻接矩阵：
   

2. 网对应的邻接矩阵：
   所谓的网就是带权图。
   

3. 邻接矩阵法的一些要点

6.2.2 邻接表法

顺序+链式存储。对图G的每个顶点建立一个单链表。与树中的孩子表示法相同。

1. 邻接表存储结构
   

2. 有向图、无向图空间复杂度
   

3. 邻接矩阵法与邻接表法对比

6.2.3 十字链表

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

前面已讲到邻接矩阵的空间复杂度高。
邻接表计算有向图的入度，寻找有向图的入边，不方便。
而十字链表可以弥补这些缺陷。

1. 十字链表
   

2. 十字链表法性能分析
   

6.2.4 邻接多重表

是无向图的一种链式存储结构。与十字链表类似。

邻接矩阵与邻接表有如下图的缺陷，引入邻接多重表可以弥补这些缺陷。

1. 邻接多重表

2. 删除边、删除节点
   

6.2.5 4种存储方式小结

6.2.6 图的基本操作