数据结构与算法 / 系统课时

邻接表

邻接表

邻接表为每个顶点维护一组实际相连的顶点,只为真实存在的边分配存储空间。它能高效枚举局部邻居,是稀疏图和图遍历算法中最常见的表示方式。本课将实现无向图邻接表,并与邻接矩阵比较查询、遍历和空间成本。

学习目标

  • 理解邻接表中顶点数组与邻接集合的组织方式。
  • 能实现添加边、删除边、查边和枚举邻接点操作。
  • 能根据顶点数、边数和访问模式选择邻接表或邻接矩阵。

结构与工作方式

邻接表通常由一个长度为 VV 的外层容器组成,第 u 个位置保存从顶点 u 出发的所有邻接点。无向边 (u, v) 需要同时把 v 加入 u 的集合,并把 u 加入 v 的集合;有向边只需要记录在起点一侧。

外层容器可以使用数组或 List,内层可使用动态数组、链表或集合。动态数组顺序遍历快,但删除指定邻接点可能需要移动元素;哈希集合能减少重复边并提供平均 O(1)O(1) 的查找与删除,但会增加额外内存。实现应根据操作需求选择内层结构。

邻接表中顶点与邻接集合的连接关系

图中每条无向边出现两次,因此无向图所有邻接集合中的元素总数是 2E2E;有向图中每条边只出现一次,总数是 EE。这也是邻接表空间复杂度写作 O(V+E)O(V + E) 的原因。

操作成本与矩阵对比

设顶点 u 的度为 deg(u)。枚举 u 的邻接点只访问真实边,时间复杂度是 O(deg(u))O(deg(u))。是否能快速查边取决于内层结构:链表或动态数组通常为 O(deg(u))O(deg(u)),哈希集合平均为 O(1)O(1)。

维度 邻接表 邻接矩阵
空间 O(V+E)O(V + E) O(V2)O(V^2)
枚举 u 的邻接点 O(deg(u))O(deg(u)) O(V)O(V)
判断 (u, v) 是否存在 取决于内层结构 O(1)O(1)
适合的图 稀疏图、遍历密集 稠密图、查边密集

邻接表并非在所有操作上都更快。若算法反复判断大量任意顶点对是否相邻,矩阵的直接下标访问更稳定;若算法主要从一个顶点扩展到它的邻居,例如深度优先搜索和广度优先搜索,邻接表通常更自然。

完整可运行示例

下面使用 LinkedHashSet 保存每个顶点的邻接集合。它既能避免重复边,又能保持插入顺序,使示例输出稳定。neighbors 返回不可修改的副本,避免调用者绕过图的接口直接破坏内部数据。

java
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class AdjacencyListDemo {

    private final String[] vertices;
    private final List<Set<Integer>> adjacencyList;

    public AdjacencyListDemo(String[] vertices) {
        this.vertices = vertices.clone();
        this.adjacencyList = new ArrayList<>();

        for (int i = 0; i < vertices.length; i++) {
            adjacencyList.add(new LinkedHashSet<>());
        }
    }

    public void addUndirectedEdge(int from, int to) {
        validateVertex(from);
        validateVertex(to);
        adjacencyList.get(from).add(to);
        adjacencyList.get(to).add(from);
    }

    public void removeUndirectedEdge(int from, int to) {
        validateVertex(from);
        validateVertex(to);
        adjacencyList.get(from).remove(to);
        adjacencyList.get(to).remove(from);
    }

    public boolean hasEdge(int from, int to) {
        validateVertex(from);
        validateVertex(to);
        return adjacencyList.get(from).contains(to);
    }

    public List<String> neighbors(int vertex) {
        validateVertex(vertex);
        List<String> result = new ArrayList<>();

        for (int neighbor : adjacencyList.get(vertex)) {
            result.add(vertices[neighbor]);
        }
        return Collections.unmodifiableList(result);
    }

    public void printGraph() {
        for (int i = 0; i < vertices.length; i++) {
            System.out.println(vertices[i] + " -> " + neighbors(i));
        }
    }

    private void validateVertex(int vertex) {
        if (vertex < 0 || vertex >= vertices.length) {
            throw new IllegalArgumentException("顶点下标越界: " + vertex);
        }
    }

    public static void main(String[] args) {
        String[] vertices = {"A", "B", "C", "D"};
        AdjacencyListDemo graph = new AdjacencyListDemo(vertices);

        graph.addUndirectedEdge(0, 1);
        graph.addUndirectedEdge(0, 2);
        graph.addUndirectedEdge(1, 3);
        graph.addUndirectedEdge(2, 3);

        System.out.println("初始邻接表:");
        graph.printGraph();
        System.out.println("B 与 C 相邻: " + graph.hasEdge(1, 2));
        System.out.println("D 的邻接点: " + graph.neighbors(3));

        graph.removeUndirectedEdge(1, 3);
        System.out.println("删除 B-D 后:");
        graph.printGraph();
    }
}

预期输出

text
初始邻接表:
A -> [B, C]
B -> [A, D]
C -> [A, D]
D -> [B, C]
B 与 C 相邻: false
D 的邻接点: [B, C]
删除 B-D 后:
A -> [B, C]
B -> [A]
C -> [A, D]
D -> [C]

边界与实现选择

无向图添加和删除边时必须更新两端,否则会产生单向残留。使用允许重复元素的 List 时,还要决定是否允许平行边;若不允许,应在插入前检查或改用 Set。自环 (u, u) 在无向图中也需要明确计数规则,因为它对顶点度的贡献通常按 2 计算。

带权图可以把邻接点编号替换为包含 to 与 weight 的边对象。有向图还可同时维护出边表和入边表,以便分别高效计算出度、入度及反向遍历。若顶点会动态增加,外层使用可扩容的 List 比固定二维矩阵更灵活。

本课练习

  1. 增加 degree(int vertex),返回无向图顶点的度,并验证删除 B-D 后顶点 B 的度从 2 变为 1。
  2. 将内层结构替换为 ArrayList<Integer>,处理重复边,并比较 hasEdge 与删除操作的复杂度变化。
  3. 扩展为带权有向图,定义边对象保存终点和权值,要求支持添加 A -> C、查询其权值并打印所有出边。

本课总结

  • 邻接表只保存真实存在的边,空间复杂度为 O(V+E)O(V + E),适合稀疏图。
  • 枚举邻接点只需访问当前顶点的邻接集合,成本是 O(deg(u))O(deg(u))。
  • 内层容器决定查边、去重、删除和遍历顺序,选择时应结合算法的主要操作。

下一课预告

接下来可以在邻接表上实现广度优先搜索和深度优先搜索,进一步观察不同图表示如何影响遍历过程、复杂度和访问顺序。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

邻接表

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通