图（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算法不同的是，Bellman-Ford算法可以处理负权边，而Dijkstra算法不能。

Floyd算法

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

图着色算法

图着色算法是一种经典的图论算法，它的目标是给图中的每个顶点分配一个颜色，使得相邻的顶点颜色不同。这种算法在寄存器分配时，非常有用。图着色算法简单实现可以用贪心算法来做，但是，贪心算法并不能保证得到最优解。