图的表示

6.1 邻接矩阵：工作原理、优缺点。

邻接矩阵 是通过使用大小为 n x n的方矩阵来表示图的一种方法，其中 n 是图中的顶点数。矩阵中的元素表示顶点之间边的存在或不存在：

• 如果顶点 i 和 j 之间存在边，那么元素 A[i][j] = 1（如果是加权图，就是边的权重）。
• 如果没有边，那么 A[i][j] = 0。

例子：

对于具有顶点 A、B、C 和边 (A, B)、(B, C) 和 (C, A) 的图，邻接矩阵将是：

如果所有顶点都相互连接，则邻接矩阵将如下所示：

优点：

• 简单：容易理解和实现。
• 快速访问：检查两个顶点之间的边的存在性在 O(1) 时间内完成。
• 适用于密集图：对于具有大量边的图有效。

缺点：

• 高内存消耗：即使图中只有少量边（稀疏图），也需要 O(n^2) 内存。
• 对稀疏图效率低：当顶点很多而边很少时，矩阵的大多数元素都会是零，从而导致内存的低效使用。

6.2 邻接表：工作原理、优缺点。

邻接表 是通过使用列表的数组来表示图的一种方法。数组的每个元素对应于图中的一个顶点，并包含与之相邻的所有顶点的列表。

例子：

对于具有顶点 A、B、C 和边 (A, B)、(B, C) 和 (C, A) 的图，邻接表将是：

如果所有顶点都相互连接，则邻接表将如下所示：

优点：

• 高效的内存使用：需要 O(V + E) 内存，其中 V 是顶点数，E 是边数，这使其更适合稀疏图。
• 遍历简便：便于执行图的遍历操作（如广度优先搜索或深度优先搜索）。

缺点：

• 更复杂的访问：检查两个顶点之间边的存在性需要 O(k) 时间，其中 k 是顶点的邻居数量。
• 结构不够直观：与邻接矩阵相比实现和理解起来更复杂。

6.3 不同图表示方法的比较。

让我们比较不同的图表示方法。

1. 邻接矩阵：

• 简单性：容易理解和实现。
• 内存：需要 O(n^2) 内存，对于稀疏图可能效率低下。
• 访问速度：检查边的存在性在 O(1) 时间内完成。
• 合适性：适用于具有大量边的密集图。

2. 邻接表：

• 简单性：不如邻接矩阵直观，但也容易理解。
• 内存：需要 O(V + E) 内存，对稀疏图更为有效。
• 访问速度：检查边的存在性在 O(k) 时间内完成，其中 k 是顶点的邻居数量。
• 合适性：适用于边少的稀疏图。

比较：

邻接矩阵 更适合于密集图，其中大多数顶点都有连接边，因为它提供了对边信息的快速访问且易于实现。

邻接表 在稀疏图中更可取，其中边的数量远少于顶点对的可能组合。它们提供了高效的内存使用并便于执行图的遍历操作。