← 首页·文章列表

Java 后端 · 10 min

图论入门：用一个故事把数据结构里的"图"讲透

#图论

图论入门：用一个故事把数据结构里的"图"讲透

📷 此处原有配图

先说个我踩过的坑

大二上数据结构期末考试，有道题让判断一个图能不能拓扑排序。我看了半天愣是没看懂题在说啥——什么是入度出度？为什么有环就不能排序？这些词我背下来了，但脑子里的东西是糊的。

后来自己重新捋了一遍才发现，这些概念从来就不是孤立的，它们是一套体系。懂了它们是怎么串起来的，什么拓扑排序、DFS 森林、环检测，全是一套东西的不同面。

这篇文章，就是把我踩过的坑从头走一遍。你跟着走一遍，保证脑子里是通的。

一、什么是图？

别被名字吓到。图，就是点和线。

现实里最直观的例子就是社交网络。

A —— B —— C
|       /
  D —— E

每个人是一个顶点（Vertex），每条好友关系是一条边（Edge）。A 认识 B，B 认识 C，这些边把顶点连起来，就是一个图。

再比如地图导航——每个路口是顶点，每条路是边，边上有距离（权重），这就是一个加权图。

所以图这个东西，数据结构里说的"图"和生活里的"图"是一回事：东西 + 东西之间的关系。

二、图里的几个基本概念

搞清楚了图是什么，接下来把这几个词搞清楚。名字听着吓人，但都是描述这套关系的自然语言。

顶点（Vertex）和边（Edge）

有向图 vs 无向图

无向图：边没有方向，A 和 B 是好友，那 B 和 A 也是好友。社交网络默认是无向的。

有向图：边有方向，A 关注了 B，但 B 不一定关注 A。微博 / 抖音的关注关系是有向的。

无向：    A —— B          有向：    A → B
         B —— A                   B  ↘
                                          C

有向图的边叫弧（Arc），无向图的边叫边（Edge）。

加权图 vs 无权图

边上有数字（距离、花费、时间）叫加权图，没数字叫无权图。地图导航就是典型的加权图。

三、图怎么存？两种方式

这是学图论最实用的部分——代码里怎么表示一个图。

邻接表

每个顶点存一个列表，列出它连向哪些顶点。

# 无向图
graph = {
    'A': ['B', 'D'],
    'B': ['A', 'C'],
    'C': ['B', 'E'],
    'D': ['A', 'E'],
    'E': ['C', 'D']
}

空间复杂度：O(V + E)，V 是顶点数，E 是边数。

邻接矩阵

一个 V×V 的二维数组，matrix[i][j] = 1 表示顶点 i 到 j 有边。

# 5个顶点的图，索引 0~4 对应 A~E
matrix = [
    [0, 1, 0, 1, 0],  # A
    [1, 0, 1, 0, 0],  # B
    [0, 1, 0, 0, 1],  # C
    [1, 0, 0, 0, 1],  # D
    [0, 0, 1, 1, 0]   # E
]

空间复杂度：O(V²)，稠密图才值得用。

什么时候用哪个？

刷题里遇到图，90% 的情况用邻接表就够了——省空间，实现遍历也直观。只有顶点数少、边数接近 V² 的稠密图才考虑矩阵。

四、图的遍历：不只是搜，还有打通整张图

图论里最重要的事之一：怎么把一张图的所有顶点都走一遍。

BFS（广度优先搜索）

一层一层往外扩。想象往水里扔一颗石子，波纹一圈一圈往外散。

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=' ')          # 访问这个顶点
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS 的核心用途：找最短路径（无权图）、层序遍历。

DFS（深度优先搜索）

一条路走到黑，再回头换条路。是递归的天然写法。

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    if node in visited:
        return
    visited.add(node)
    print(node, end=' ')             # 访问这个顶点
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

DFS 的核心用途：拓扑排序的前置、连通分量检测、找环。

BFS 和 DFS 不是一个算法，是两种策略

BFS 适合"最近"优先，DFS 适合"先探深"优先。刷题里经常需要根据题目性质选一个——或者两个都试试看哪个对。

五、入度、出度、连通性

这几个概念是拓扑排序的直接前置，必须搞清楚。

度（Degree）

        A → B
        ↓   ↓
        C → D

A 的出度=1，入度=0
B 的出度=0，入度=2

连通性（Connectivity）

无向图：任意两个顶点之间有没有路连通。 有向图：分两类——强连通（有向路径来回都行）和弱连通（忽略方向后能连通）。

环（Cycle）

从一个顶点出发，沿着边的方向走，能回到自己——这就是环。

A → B → C → A  （有向环）
A — B — C — A  （无向环）

有向环是拓扑排序的天敌——这是我们后面要重点讲的。

📷 此处原有配图

六、拓扑排序：终于说到正题

终于到这了。先说清楚它是什么，再说怎么做。

拓扑排序是什么

在一个有向无环图（DAG）里，把所有顶点排成一个线性序列，使得每条有向边都满足：起点在终点前面。

举个例子——穿衣顺序：

内衣 → 外套
  ↓     ↓
裤子 → 鞋子

你不能先穿鞋子再穿裤子。拓扑排序就是要找出这样一个顺序。

核心条件：图必须是有向无环图（DAG）。有环的话，根本不存在这样的顺序——因为环里每个点都在其他点后面，形成死循环。

Kahn 算法（最直观）

思路简单到惊人：每一步找一个人度为 0 的顶点，输出它，然后删掉它出发的边。重复直到所有顶点都输出。

from collections import deque

def topological_sort_kahn(graph, indegree):
    queue = deque([v for v in range(len(indegree)) if indegree[v] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return result if len(result) == len(graph) else []  # 有环时返回空

为什么能工作：入度为 0 说明没有别的顶点指向它——没有"必须在它前面"的东西，所以它可以第一个出来。删掉它的边之后，又有新的顶点入度变成 0，重复这个过程。

时间复杂度：O(V + E)，每个顶点和每条边各处理一次。

DFS 版（递归思路）

思路和 Kahn 正好反过来：先 DFS 走到底，然后逆序输出。

def dfs_topo(node, graph, visited, on_stack, result):
    visited[node] = True
    on_stack[node] = True
    for neighbor in graph[node]:
        if on_stack[neighbor]:          # 递归栈里出现了邻居→有环
            raise ValueError("有环！无法拓扑排序")
        if not visited[neighbor]:
            dfs_topo(neighbor, graph, visited, on_stack, result)
    on_stack[node] = False
    result.append(node)                 # 后序加入，最后逆序输出

def topological_sort_dfs(graph):
    n = len(graph)
    visited = [False] * n
    on_stack = [False] * n
    result = []
    for i in range(n):
        if not visited[i]:
            dfs_topo(i, graph, visited, on_stack, result)
    return result[::-1]

DFS 版的原理：后序遍历（先处理完所有后继节点再处理当前节点）保证了每个节点的"后继"都排在它前面。逆序输出之后，每个节点的"后继"就变成了"在它后面"。

核心原理就一句话：Kahn 是逐步把"入度为 0 的顶点"摘出来，DFS 是通过后序 + 逆序天然满足拓扑序要求。

有环 vs 无环：怎么判断？

Kahn 算法里，如果最终输出的顶点数小于总顶点数，说明图里有环——有些顶点永远没办法入度归零。

def has_cycle(graph):
    indegree = [0] * len(graph)
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] += 1
    queue = deque([v for v in range(len(indegree)) if indegree[v] == 0])
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return count != len(graph)

七、刷题里怎么用

学了这些概念，刷题的时候怎么用？

场景一：课程优先级（拓扑排序裸题）

课程 A 是课程 B 的先修课，给定课程关系，判断能完成所有课程。

这题本质就是拓扑排序，看图中有没有环。

场景二：任务调度

有 N 个任务，有些任务必须在其他任务完成之后才能开始，求一个合法执行顺序。

同样是拓扑排序的应用。

场景三：依赖关系解析

给定包依赖关系，判断安装顺序或检测循环依赖。

这是 Kahn 算法最经典的应用场景。

场景四：检测环

判断有向图里有没有环。

用拓扑排序的思路，入度始终不为 0 的顶点就在环里。

一个刷题tip

刷图论题，最重要的习惯是先想清楚图是怎么建的——顶点是什么，边是什么，有向还是无向，加权还是不加权。图建对了，后面的算法就是顺水推舟。

📷 此处原有配图

八、这些东西是怎么串在一起的

写到最后，回头看一眼这整张图是怎么连起来的：

有向图
  ├── 环检测 ←──→ 拓扑排序的前置
  ├── 入度/出度 ←──→ Kahn 算法的核心
  ├── DFS 遍历 ←──→ DFS 版拓扑排序
  └── 连通性 ←──→ 强连通分量（进阶内容）

入度/出度是拓扑排序的操作对象，环检测和拓扑排序是一枚硬币的两面——能拓扑排序的图一定无环，无环的图一定能拓扑排序。

它们从来就不是孤立的八个子题，是一张网上相邻的节点。

搞懂了这张网，面试里遇到图论题，你脑子里不是背过的模板，而是一张活的图。