图的表示与存储
一、邻接矩阵
邻接矩阵是一种表示图（Graph）的方法，它使用一个二维矩阵来表示图中的顶点和边。邻接矩阵适用于存储稠密图（Dense Graph），因为它能够直观地展示顶点之间的连接关系。
以下是邻接矩阵的基本构造和特点：
-
矩阵表示：
- 如果一个图有 ( V ) 个顶点，则邻接矩阵是一个 ( V \times V ) 的矩阵 ( A )。
- 如果存在一条从顶点 ( i ) 到顶点 ( j ) 的边，则 ( A[i][j] ) 为1（或表示权重的值）；如果不存在边，则 ( A[i][j] ) 为0。
-
无向图：
- 在无向图中，边 ( (i, j) ) 和 ( (j, i) ) 是相同的，因此邻接矩阵是对称的，即 ( A[i][j] = A[j][i] )。
-
有向图：
- 在有向图中，边 ( (i, j) ) 和 ( (j, i) ) 是不同的，因此邻接矩阵不一定对称。
例如，考虑一个有4个顶点（0, 1, 2, 3）的无向图，边为：0-1, 0-2, 1-2, 2-3。这个图的邻接矩阵表示如下：
0 1 2 3
——————————————————————————————————————————
0 | 36767 1 1 36767
1 | 1 36767 1 36767
2 | 1 1 36767 1
3 | 36767 36767 1 36767
在实际应用中，邻接矩阵有以下优点和缺点：
优点：
- 快速查找：可以在 ( O(1) ) 时间内检查两个顶点之间是否存在边，因为只需检查矩阵中的一个元素。
- 简单表示：邻接矩阵的表示形式简单直观，易于理解和实现。
缺点
- 空间消耗大：邻接矩阵需要 ( V^2 ) 个存储单元，对于稀疏图（Sparse Graph）而言，空间效率低下。
- 遍历相邻顶点效率低：遍历一个顶点的所有相邻顶点需要 ( O(V) ) 的时间，因为需要检查整行或整列。
特性
特性1：无向网的邻接矩阵是对称的。
特性2：顶点i的度等于第i行中非极大值（32767）的个数。
特性3：邻接矩阵常用于图论中的算法研究，尤其是在图比较稠密的情况下。它也在某些网络和关系表示中有广泛应用。
二、邻接表
邻接表是一种用于表示图（Graph）数据结构的方法。图由顶点（Vertices）和边（Edges）组成，邻接表通过记录每个顶点的相邻顶点来表示图的结构。相比于邻接矩阵，邻接表在存储稀疏图时更加节省空间。
以下是邻接表的基本构造和特点：
-
顶点列表：
- 图的每个顶点都有一个列表或链表来存储与之相邻的顶点。
- 这些列表或链表通常存储在一个数组或哈希表中，数组的每个索引或哈希表的每个键对应一个顶点。
-
边列表：
- 对于每个顶点，邻接表记录该顶点的所有相邻顶点。
- 每个顶点的相邻顶点可以用链表、动态数组或其他合适的数据结构存储。
例如，考虑一个图有4个顶点（0, 1, 2, 3），以及以下边：0-1, 0-2, 1-2, 2-0, 2-3, 3-3。这个图的邻接表表示如下：
顶点 邻接顶点
0: 1 -> 2
1: 2
2: 0 -> 3
3: 3
在实际应用中，邻接表有以下优点和缺点：
优点
- 节省空间：对于稀疏图，邻接表比邻接矩阵更节省空间。邻接矩阵需要存储 (V^2) 个元素（V是顶点数），而邻接表只需要存储边的数量。
- 高效遍历：可以高效地遍历每个顶点的相邻顶点。
缺点
- 查询某一对顶点是否相邻不如邻接矩阵高效：需要遍历列表来查找是否存在一条边。
- 不适合存储密集图：对于密集图，邻接表的优势减小，因为存储的边数接近于顶点数的平方。
特性
特性1：邻接表不唯一。
特性2：若无向网中有n个顶点、e条边，则其邻接表需要n个头结点和2e个表结点。存储稀疏图比较合适。
特性3：无向网中顶点Vi的度为第i个单链表中的结点数。
特性4：邻接表出度易找，入度难找。逆邻接表出度难找，入度易找。
特性5：邻接表常用于算法和数据结构课程中，也在实际的网络、社交媒体分析等领域有广泛应用。
三、邻接矩阵和邻接表的区别和用途
区别
（1）对于任一确定的无向网，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一。
（2）邻接矩阵的空间复杂度是O(n^2)，邻接表为O(n + e)。
（3）邻接矩阵的时间复杂度是O(n^2)，邻接表为O(elog2(e))。
用途
邻接矩阵多用于稠密图。
邻接表多用于稀疏图。
