图论算法：邻接表与遍历

图论算法入门：从邻接表到图的遍历

图是计算机科学中最强大、最灵活的数据结构之一，它能表示网络、社交关系、地图路径等几乎所有存在“关联”的场景。要驾驭图算法，首先要解决两个基础问题：如何存储图，以及如何系统地访问图中的节点。本文将带你掌握最实用的存储方式——邻接表，以及两种核心遍历策略——深度优先搜索（DFS）和广度优先搜索（BFS）。

为什么选择邻接表？理解图的存储

存储图的方式主要有两种：邻接矩阵和邻接表。邻接矩阵用 V x V 的二维数组表达边，虽然查询任意两点是否相连只需 O(1) 的时间，但对于稀疏图（边的数量远小于节点数量的平方），它会浪费大量空间。邻接表正是为解决这一痛点而生的，它只为实际存在的边分配空间，空间复杂度为 O(V + E)，是大多数图算法的默认存储结构。

邻接表的底层结构

邻接表通常由一个数组或列表组成，其中每个位置对应图中的一个节点。每个元素又是一个链表、数组或动态列表，用于存放从该节点出发直达的所有邻居节点。

无向图的邻接表：边 (u, v) 会使 u 的列表中出现 v，v 的列表中出现 u。

有向图的邻接表：仅在有向边 u -> v 的方向上，将 v 加入 u 的邻居列表。

带权图的邻接表：列表中的元素不再只是目标节点编号，而是存储(目标节点, 权重)这样的对。

代码实现：构建邻接表

以下示例用Python展现，思路可以轻松迁移到任何语言。

# 假设节点编号从0到V-1
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        # 初始化一个列表，其中有V个空列表
        self.adj = [[] for _ in range(vertices)]

    # 添加无向边
    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    # 添加有向边（如果有向）
    def add_directed_edge(self, u, v):
        self.adj[u].append(v)

    # 打印邻接表，方便查看
    def print_graph(self):
        for i in range(self.V):
            print(f"顶点 {i}: {self.adj[i]}")

对于一个拥有5个顶点和边(0-1, 0-4, 1-2, 1-3, 1-4, 2-3, 3-4)的无向图，输出的邻接表直观展示了每个节点的邻居：

顶点 0: [1, 4]
顶点 1: [0, 2, 3, 4]
顶点 2: [1, 3]
顶点 3: [1, 2, 4]
顶点 4: [0, 1, 3]

不同语言的邻接表实现

邻接表思想不变，但不同语言有各自的惯用方式：

• C++：vector<vector<int>> adj;，或需要权重时用 vector<vector<pair<int, int>>> adj;
• Java：List<List<Integer>> adj = new ArrayList<>();，并逐个初始化内部 ArrayList
• JavaScript：可以用数组的数组，或使用 Map 键为节点、值为邻居数组，对非连续编号友好

无论哪种语言，核心都是将图映射为“节点->邻居列表”的结构。

图的遍历：访问节点的艺术

有了存储结构，下一个自然的问题是：如何不重复、不遗漏地访问图中所有节点？这就是图的遍历，也是路径查找、连通性判断、拓扑排序等复杂算法的基石。我们通常有两种遍历思想：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）：“一条路走到黑”

DFS的策略是从起点出发，沿着一条路径尽可能深入，直到无法继续，然后回溯到上一个分叉点，继续探索其他分支。就像走迷宫时始终贴着左手墙走，直到碰壁再回头换另一条路。

递归实现最契合DFS的自然回溯特性：

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')  # 访问节点
    
    for neighbor in graph.adj[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

迭代实现使用显式的栈来模拟递归过程（需要手动管理访问状态和回溯）：

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            # 注意：为了保持顺序一致，可以将邻居逆序压栈，或按需调整
            for neighbor in reversed(graph.adj[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

DFS的时间复杂度为 O(V + E)，因为它会访问每个顶点一次，并遍历所有顶点的邻接边总计 2E 次（无向图）或 E 次（有向图）。空间复杂度取决于递归调用栈深度或显式栈的大小，最坏情况下可能达到 O(V)。

广度优先搜索（BFS）：“逐层扩展”

BFS则采用完全不同的策略：从起点开始，先访问所有距离为1的邻居，再访问距离为2的邻居，以此类推。这种“层次化”的进展天然适合寻找最短路径（在无权图中）或按层处理信息。BFS的核心数据结构是队列。

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()  # 取出队首
        print(vertex, end=' ')
        
        for neighbor in graph.adj[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS同样具有 O(V + E) 的时间复杂度，每个顶点和每条边都被处理一次。空间方面，队列中可能同时保存最多的一层节点，这在宽而浅的图中可能接近 O(V)。

DFS vs BFS：场景选择指南

选择建议：

• 需要找最短路径（边数最少）时，用 BFS。
• 需要遍历所有可能性、回溯搜索（如排列组合、迷宫所有路径）时，DFS 递归写法更简洁。
• 检测环路、拓扑排序、强连通分量等问题，DFS 的性质使其更易实现。

遍历算法的实战深度：不止于打印

仅仅遍历并打印节点只能算是入门。真正的图算法中，DFS 和 BFS 是作为骨架嵌入更复杂逻辑中。以下是两个关键扩展技巧：

记录遍历层级与父节点（BFS 变体）

在 BFS 过程中，我们可以顺带记录每个节点到起点的距离，以及它在搜索树中的父节点，从而重建最短路径。

def bfs_shortest_path(graph, start, target):
    visited = {start}
    queue = deque([start])
    parent = {start: None}   # 父节点字典
    distance = {start: 0}    # 距离字典

    while queue:
        current = queue.popleft()
        if current == target:
            break
        for neighbor in graph.adj[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = current
                distance[neighbor] = distance[current] + 1
                queue.append(neighbor)
    
    # 重建路径
    path = []
    if target in parent:
        step = target
        while step is not None:
            path.append(step)
            step = parent[step]
        path.reverse()
    return path, distance.get(target, -1)

检测连通分量（DFS / BFS 均可）

一个图可能由多个互不连通的子图组成。我们可以通过多次调用遍历算法，标记每个顶点所属的连通分量。

def connected_components(graph):
    visited = set()
    components = []
    for v in range(graph.V):
        if v not in visited:
            # 开始一个新的遍历，收集该分量所有节点
            comp = set()
            # 使用 DFS 或 BFS 均可，这里用 DFS 递归收集
            def dfs_collect(node):
                visited.add(node)
                comp.add(node)
                for nb in graph.adj[node]:
                    if nb not in visited:
                        dfs_collect(nb)
            dfs_collect(v)
            components.append(comp)
    return components

小结：从工具到思维

邻接表与两种遍历算法，是图论世界的通用语言。当你能熟练使用邻接表表示任意图，并能灵活运用 DFS 的“纵深探索”和 BFS 的“层次推进”，就获得了解决绝大多数图问题的基本框架。后续无论是学习最小生成树、最短路径（Dijkstra、Floyd），还是网络流、强连通分量，你都会发现它们不过是这两种核心思想在各种约束下的精妙变形。

将下面的练习作为思维检验：

1. 用邻接表实现一个有向图，并尝试用 DFS 检测有向图中是否存在环。
2. 使用 BFS 解决“单词阶梯”问题：从一个单词变换为另一个，每次只能改变一个字母，且中间词必须在给定词典中，求最短变换路径长度。

牢固的基础将让你在图算法的道路上越走越远。