一、先认识图：顶点和边的关系¶
在数据结构中，图是由“顶点（Vertex）”和“边（Edge）”组成的结构。比如我们熟悉的社交网络：每个用户是一个顶点，用户之间的“好友关系”就是边。再比如城市交通图：每个城市是顶点，城市间的“道路”就是边。
二、邻接矩阵：最直观的存储方式¶
邻接矩阵是图最基础的存储方式，它用一个二维数组表示图。数组的行和列对应图的顶点，数组中的值（0或1）表示两个顶点之间是否有边（1表示有边，0表示无）。
举个例子：
假设有3个顶点（0、1、2），边有：0-1、1-2。
邻接矩阵可以表示为：
0 1 2
0 0 1 0
1 1 0 1
2 0 1 0
- 第i行第j列的值
matrix[i][j]表示顶点i和顶点j之间是否有边。 - 比如
matrix[0][1] = 1，说明顶点0和1之间有边；matrix[2][1] = 1，说明顶点2和1之间有边。
三、邻接表：“邻居链表”式的存储¶
邻接表是另一种更灵活的存储方式，它为每个顶点单独维护一个链表（或动态数组），用来存储与该顶点直接相连的所有“邻居”。
同样以上面的例子：
顶点0的邻居是1，所以邻接表为 0: [1]；
顶点1的邻居是0和2，所以邻接表为 1: [0, 2]；
顶点2的邻居是1，所以邻接表为 2: [1]。
简单说：每个顶点后面跟着它的“邻居列表”，没有邻居的顶点（孤立顶点）邻接表为空。
四、对比：邻接矩阵 vs 邻接表¶
| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间占用 | 需 n² 空间（n为顶点数），无论边多少都占满n²个位置。 |
仅占 n + e 空间（e为边数），只存实际存在的边。 |
| 查找边 | 直接查二维数组，时间 O(1)（比如查顶点i和j是否有边，看 matrix[i][j]）。 |
需遍历顶点i的邻接表，时间 O(degree(i))（degree(i)是顶点i的邻居数）。 |
| 遍历邻居 | 需遍历整个一行（比如顶点i的邻接行），时间 O(n)（不管有没有边，都要检查n个位置）。 |
只需遍历邻接表，时间 O(degree(i))（只访问实际存在的边）。 |
五、邻接表为什么更好？¶
核心优势：针对“稀疏图”的高效性
在实际问题中，大多数图是稀疏图（比如社交网络中，每个人的好友数远少于总人数）。此时：
- 邻接矩阵 会浪费大量空间（比如1000个顶点的图，若只有1000条边，邻接矩阵仍需1000×1000=100万空间，而邻接表只需1000+1000=2000空间）。
- 邻接表 只存实际边，空间效率更高；遍历邻居时，也只访问存在的边，时间效率更高。
例外情况：如果是稠密图（比如完全图，每个顶点都和其他所有顶点相连），邻接矩阵可能更合适（但这种情况较少见）。
六、总结¶
邻接表是稀疏图的“高效存储神器”，它通过“邻居链表”的方式，用更少的空间存储实际边，并更快地遍历顶点的邻居。相比之下，邻接矩阵虽然直观，但在大多数实际场景中（尤其是稀疏图），邻接表是更优选择。
在编程中，邻接表是处理图问题（如最短路径、拓扑排序）的主流存储方式，也是初学者需要掌握的核心数据结构之一。
简单一句话记住：邻接表是“只存朋友的列表”，比邻接矩阵这个“存所有人的表格”更省空间、更快！