图的存储

• 邻接矩阵 (Adjacency Matrix)：
  • 结构：二维数组 A[n][n]。
  • 特点：
    • 无向图矩阵对称，可压缩存储（只存上/下三角）。
    • 空间复杂度 $O(n^2)$，适合稠密图。
    • 顶点的度 = 第 $i$ 行（或列）非零元素之和。
• 邻接表 (Adjacency List)：
  • 结构：顶点表（数组） + 边表（链表）。
  • 特点：
    • 空间复杂度 $O(n+e)$，适合稀疏图。
    • 有向图中，邻接表易求出度，逆邻接表易求入度。