教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

邻接表

介绍

邻接表是图论中最常用的图表示方式之一,它为每个顶点维护一个列表,存储与该顶点相邻的所有顶点。这种表示方法特别适合表示稀疏图(边数远小于顶点数平方的图),能有效节省空间,保持较高的操作效率。

基本概念

邻接表(Adjacency List)是一种通过链表或数组表示图的数据结构。在理解它之前,我们需要掌握一些基础图论概念:

图(Graph):由顶点(Vertex)和连接顶点的边(Edge)组成的数据结构。图可以用来表示现实世界中的各种关系,如社交网络、交通系统等。

顶点(Vertex):图中的节点,通常用数字或字母标识,如 0, 1, 2... 或 A, B, C...

边(Edge):连接两个顶点的线段,表示它们之间存在某种关系。

在邻接表中:

  • 每个顶点对应一个列表(可以是链表、数组或其他集合类型)
  • 列表中存储与该顶点直接相连的所有顶点
  • 对于有权图,还需要存储边的权重信息

邻接表的表示方式根据图的类型有所不同:

...

目录