数据结构-图的存储结构

图的存储结构

---

邻接矩阵

---

邻接矩阵的主要特点：
①方便查找任意一个顶点是否存在边。

②方便找任一个顶点的所有“邻接点”（有边直接相连的顶点）。

③方便计算任一顶点的度。

④无向图的邻接矩阵数组一定是一个对称矩阵。

⑤对于无向图，邻接矩阵数组的第i行或第i列非零元素、非∞元素的个数正好是顶点i的度。

⑥对于有向图，邻接矩阵数组的第i行（或第i列）非零元素、非无穷元素的个数正好是顶点i的出度（或入度）。

⑦在邻接矩阵中，判断图中两个顶点之间是否有边或者求两个顶点之间的权的执行时间为O(1)。

⑧一个图的邻接矩阵表示是唯一的。

---

图的邻接矩阵存储类型定义如下：

---

邻接表

例：

例题：

---

邻接表的特点：
①邻接表表示 不唯一

②方便找任意顶点的所有“邻接点”。

③若无向图中有N个顶点，e条边，则其邻接表需要N个头结点+2e个表结点。邻接表的存储空间为O（n+2e）、有向图：O（n+e）。

④特别适合稀疏图存储。

⑤无向图中顶点V_i。的度为第i个单链表的结点数。

⑥方便计算任意顶点的度（无向图）。

⑦有向图（就算出度方便，入度不方便）。

---

图的邻接矩阵和邻接表两种存储结构各有什么优缺点？