邻接表
介绍
邻接表是图论中最常用的图表示方式之一,它为每个顶点维护一个列表,存储与该顶点相邻的所有顶点。这种表示方法特别适合表示稀疏图(边数远小于顶点数平方的图),能有效节省空间,保持较高的操作效率。
基本概念
邻接表(Adjacency List)是一种通过链表或数组表示图的数据结构。在理解它之前,我们需要掌握一些基础图论概念:
图(Graph):由顶点(Vertex)和连接顶点的边(Edge)组成的数据结构。图可以用来表示现实世界中的各种关系,如社交网络、交通系统等。
顶点(Vertex):图中的节点,通常用数字或字母标识,如 0, 1, 2... 或 A, B, C...
边(Edge):连接两个顶点的线段,表示它们之间存在某种关系。
在邻接表中:
- 每个顶点对应一个列表(可以是链表、数组或其他集合类型)
- 列表中存储与该顶点直接相连的所有顶点
- 对于有权图,还需要存储边的权重信息
邻接表的表示方式根据图的类型有所不同:
...