图（Graph）

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

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

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

图论在编译中的应用

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

图的表示法

邻接矩阵

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

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

邻接表

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

边表

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

拓扑排序

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

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

图的遍历

图的遍历方式有两种，一种是深度优先遍历，另一种是广度优先遍历。

最小生成树

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

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

最短路径

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

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

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

对于多源最短路问题，有一种经典的算法，叫做Floyd算法。

图着色算法

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