图（Graph）

图(Graph)是由顶点的有穷非空集合和顶点之间的集合组成，通常表示为G(V,E)，其中G 表示一个图，V是图G中顶点的集合，E是图G中边的集合。在描绘一张图的时候，通常用一组点或小圆圈表示节点，其间的边则使用直线或曲线。

试一试，在下面这个图中，添加一些顶点和边。

图中的边可以是有方向或没有方向的，有方向的称为有向图，没有方向的称为无向图。上面的图有箭头表示，是有向图。有时，图上的边会存在权重，用来表示，路程、花费、时间等。这种被称为加权图。

图论在编译中的应用

图论在编译中的应用非常广泛，比如，编译器的词法分析阶段，就是使用有限状态自动机来实现的。有限状态自动机可以看作是一种特殊的有向图。对于函数内各种分支循环构成的代码运行结构，我们一般构建控制流图来表示。我们在追踪程序中的函数调用时，往往喜欢用调用图来表示。在寄存器分配时，图着色算法也是一种图论算法。在代码优化时，可以使用数据流分析，来分析程序中的数据流，这也是一种图论算法。

图的表示法

邻接矩阵

邻接矩阵是一种常见的表示图的方法，使用一个二维表，行列都是定点的编号。如果两个顶点之间存在边，则在对应的行列位置上标记为1或者对应权重，否则标记为0。

这种方式简单直观，并且对于无向图，邻接矩阵是对称的。但是，对于稀疏图，邻接矩阵会浪费大量的空间，因为其大部分的位置都是0。

试一试，在左侧编辑图结构，右侧会实时显示对应的邻接矩阵表示法。下方示例为有向图；开启 :allow-weight="true" 可编辑边权重。

加权图示例：

无向图示例（邻接矩阵对称）：

邻接表

邻接表是一种更加节省空间的表示图的方法，它使用一个数组，数组中的每个元素都是一个链表，链表中存储了与该顶点相邻的顶点。

试一试，在左侧编辑图结构，右侧会实时显示对应的邻接表表示法。

边表

边表则是一种以边为中心的表示图的方法，它使用一个数组，数组中的每个元素都是一条边，边中存储了起点和终点的顶点编号，以及权重等信息。一般边表需要排序或建立索引，以便快速查找哪些定点与某个顶点相邻。在数据库中存储图结构，如用户的好友、关注关系等，就十分常用这种表示方法。

试一试，在左侧编辑图结构，右侧会实时显示对应的边表表示法。下方示例为加权有向图。

拓扑排序

有些图会有一些特殊的性质，比如，有向无环图（DAG）就是一种特殊的图，它的顶点之间存在有向边，但是不存在环。这种图的一个重要性质是，它的顶点可以被线性排序，使得对于所有的有向边(u,v)，都有u在v之前。这种排序被称为拓扑排序。

拓扑排序的应用非常广泛，最常见的是在构建系统中，我们需要对各个模块进行编译，但是，有些模块之间存在依赖关系，比如，模块A依赖于模块B，那么，我们就需要先编译模块B，再编译模块A。如果我们将各个模块看作图中的顶点，模块之间的依赖关系看作有向边，那么，我们就可以使用拓扑排序来确定编译的顺序。

图的遍历

图的遍历方式有两种，一种是深度优先遍历，另一种是广度优先遍历。这两种遍历方式是最为常用地访问所有节点的顺序。

深度优先遍历

深度优先，顾名思义，是顺着一条路往下走，让访问深度越深越好，直到走不下去了，才回溯访问其他兄弟节点，直到所有节点都被访问过为止。深度优先遍历一般借助栈（或递归的调用栈）来实现：访问一个节点时将其压栈，沿着某个未访问的邻居继续深入，当当前节点的所有邻居都访问完毕后再出栈回溯。

广度优先遍历

广度优先则想法，是把起始点的所有邻居节点都访问一遍，然后依次访问它们的邻居节点，直到所有节点都被访问过为止。广度优先遍历一般借助队列来实现：从起点开始，把每个访问到的节点的未访问邻居依次入队，再按入队顺序依次出队访问，因此它是一层一层向外扩展的。

试一试，在左侧编辑图结构（默认无向图），在右侧选择遍历算法与起点，点击「播放」即可观看深度优先 / 广度优先遍历的逐步动画，红色为当前节点、绿色为已访问、橙色为待处理（在栈 / 队列中）。

最小生成树

最小生成树问题是图论中的一个经典问题，它的目标是在一个加权连通图中找到一个生成树，使得树上所有边的权值之和最小。

最小生成树问题有两种经典的算法，一种是Prim算法，另一种是Kruskal算法。

最短路径

最短路径问题是图论中的另一个经典问题，它的目标是在一个加权连通图中找到两个顶点之间的最短路径。

最短路问题分为单源最短路和多源最短路，单源最短路是指从一个顶点到其他所有顶点的最短路径，多源最短路是指任意两个顶点之间的最短路径。

对于单源最短路问题，有两种经典的算法，一种是Dijkstra算法，另一种是Bellman-Ford算法。 对于多源最短路问题，有一种经典的算法，叫做Floyd算法。

Dijkstra算法

Dijkstra算法求解单源最短路，是一种贪心算法，它的基本思想是，从起点开始，每次选择距离起点最近的顶点，然后更新与该顶点相邻的顶点的距离。这个过程会一直持续到所有的顶点都被访问过为止。同时，用更新后的原点到各个顶点的距离，来决定下一步选择哪个顶点。

这种思想打个比方，如果我们从A村到B村，有两种方案，一条是坐公交直达速度比较慢，一个是先步行去停车场取车，然后开车去B村，速度比较快。如果我们发现，步行去停车场取车，然后开车去B村，速度比较快，那么，我们就会选择这个方案，并记下了，现在去B村最优方案是先步行去停车场取车，然后开车去B村。那么下一次，当我们想从A村到C村经过B村时，A村到B村的最好方法，我们就会用当前这个最优方案来计算。

堆优化

如果每次都遍历一遍所有顶点，找到距离起点最近的顶点，时间复杂度是O(n^2)，这时合适的数据结构就能辅助解决问题了。如果使用堆来优化，时间复杂度可以降到O(nlogn)。如果你还不了解堆的工作原理，可以先看看之前写的堆一章节。

Bellman-Ford算法

Bellman-Ford 也求单源最短路，但思路和 Dijkstra 完全不同：它不做「每次取出当前最近的未确定顶点」这种贪心，而是反复对所有边做松弛（relaxation）。

设起点为 $s$，令 $\mathrm{dist}[s] = 0$，其余顶点 $\mathrm{dist}[\cdot] = +\infty$。对一条边 $(u,v)$（权为 $w$），若发现

$$\mathrm{dist}[v] > \mathrm{dist}[u] + w$$

就把 $\mathrm{dist}[v]$ 更新为 $\mathrm{dist}[u] + w$——这叫一次松弛。Bellman-Ford 的做法是：把「对图中每一条边都松弛一遍」当作一轮，一共做 $|V|-1$ 轮。

为什么是 $|V|-1$ 轮？因为不含负环的最短路径最多经过 $|V|-1$ 条边；第 $k$ 轮结束时，所有「至多 $k$ 条边」的最短路都已经算对。再多一轮若还能松弛成功，说明存在从 $s$ 可达的负权环——沿环走一圈总权变小，最短路无下界，算法据此可以报错。

和 Dijkstra 对比：

	Dijkstra	Bellman-Ford
思想	贪心：每次确定一个最近点	动态规划 / 反复松弛所有边
负权边	一般不能（会算错）	可以
负环检测	通常不负责	第 $
复杂度（边表）	堆优化约 $O(E\log V)$	$O(VE)$

因此：边权非负时优先 Dijkstra；有负权、或需要检测负环时用 Bellman-Ford。还有一种常见加速叫 SPFA（用队列只松弛「可能变短」的顶点），最坏仍可能很慢，但平均往往快于朴素 Bellman-Ford。

Floyd算法

Floyd（Floyd–Warshall）求的是多源最短路：任意两点 $i,j$ 之间的最短距离，一次算完。它也是动态规划，状态可以记成：

$$d_{k}[i][j] = \text{只允许经过编号}\le k\text{的中间点时，}i\text{到}j\text{的最短路}$$

转移是「要不要经过点 $k$」：

$$d_{k}[i][j] = \min\big(d_{k-1}[i][j],\; d_{k-1}[i][k] + d_{k-1}[k][j]\big)$$

实现上通常用一个二维数组原地更新，三层循环：

初始化：d[i][j] = 边权(i,j)，无边则为 ∞，d[i][i] = 0
for k in 1..n:
    for i in 1..n:
        for j in 1..n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

外层 $k$ 表示「新允许作为中转的顶点」；内两层枚举所有起点、终点。复杂度 $O(n^3)$，空间 $O(n^2)$，适合顶点不太多、需要全源结果的场合。它同样能处理负权边；若某个 $d[i][i]$ 变成负数，则存在经过 $i$ 的负环。

和「对每个起点各跑一遍 Dijkstra / Bellman-Ford」比：稠密图或需要全部点对时，Floyd 实现简单、常数小；稀疏图且只关心少数源点时，多次单源往往更划算。

图着色算法

图着色要给每个顶点涂一种颜色，使得相邻顶点颜色不同。所用颜色的最少种数叫做色数 $\chi(G)$。判定「能否用 $k$ 种颜色着色」对一般图是 NP 难的，因此实践中多用启发式。

最简单的是贪心着色：按某个顶点顺序依次染色，每个顶点选「当前邻居还没用过的、编号最小的颜色」。颜色数不超过 $\Delta+1$（$\Delta$ 为最大度数），但顺序不同结果差很多，贪心不保证最优。常见改进是按度数从大到小排（Welsh–Powell），或结合图的特殊结构（二分图 2-色、弦图可用完美消元序最优着色等）。

在编译器里，图着色最经典的用途是寄存器分配：把「同一时刻不能共存的变量」连成干涉图（interference graph），颜色对应物理寄存器。颜色不够（寄存器不够）时，就要把某些变量溢出到内存，再继续尝试着色——这也是 Chaitin 一类分配算法的基本骨架。前文「图论在编译中的应用」里提到的，就是这件事。