图论经典问题（拓扑排序、最短路径、最小生成树）

拓扑排序

G是有n个顶点的有向图，G的拓扑排序是对G的每条边 $(v_i,v_j)$ 来说G的顶点的顺序 $v_1,...,v_n$ ，这种情况下i<j。也就是说，拓扑排序是一种排序，使得G的有向路径以增加的顺序遍历顶点。需要注意的是一个有向图可能不止有一个拓扑排序。

在有向图中以顶点表示活动，有向边表示活动之间的先后关系，这样的图称为AOV网。拓扑排序就是将各活动排一个先后次序

命题：G有一个拓扑排序当且仅当它是非循环的

做法：1.从有向图中选一个没有前驱的顶点，并且输出 2.删除该顶点以及以它为起点的边。重复这两个步骤。直到找不到没有前驱的点

应用： - 判断是否有环（无环图的所有点都能进行拓扑排序） - 课程安排问题

代码： ？

最短路径

定义G为加权图，路径的长度（或权重）是P的边的权重的总和。图中顶点u到顶点v之间的距离表示为 $d(u,v)$ ，是从u到v之间长度最短的路径，如果这样的路径存在的话

Dijkstra算法

我们对V中的每个顶点 $v$ 定义一个标签 $D[v]$ ，存储目前为止从 $s$ 到 $v$ 找到的最好的路径的长度。首先，对每个 $v≠s,D[s]=0$ 并且 $D[v]=∞$ ，然后定义 $C$ 集合，初始状态下是空集合。在算法的每次迭代总，选择不在 $C$ 中有最短的 $D[u]$ 标签的顶点 $u$ ，然后把 $u$ 放进 $C$ 。一旦新顶点 $u$ 被放进 $C$ 中，接下来更新每个邻近 $u$ 并且在 $C$ 之外的顶点v的标签 $D[v]$