图论入门题

图论简介：

图（Graph）

图可以被表示为 G={V, E}，其中 V={v1, ... , vN}表示n个点，E= {e1, ... , eM}表示m条边。

常用的储存方式包括邻接表和邻接矩阵。

连通分量（Connected Component）：各节点间至少存在一条边可以连通。

最短路算法：

Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的未被扩展的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。Dijkstra算法每一次操作分两步：

（1）找到所有未被更新过的节点中，与源点距离最短的点k。

（2）用该节点更新所有点与源节点的距离：

Floyd算法与前两种算法不同，它是求解顶点之间两两最短距离。其基本思想是，如果节点i.k的距离加上k,j的距离小于i,j的距离，则更新i,j的距离。该思想与动态规划的思想类似。需要注意的是，在枚举的过程中，需要先枚举k，再枚举ij。Floyed算法时间复杂度为O(N³)。虽然该复杂度与枚举起始节点的Dijkstra算法一致，但是Floyed算法常数复杂度比Dijkstra小很多。

拓补排序：

拓扑排序是对一个有向图构造拓扑序列，解决工程是否能顺利进行的问题。构造时有 2 种结果：

1. 此图全部顶点被输出：说明说明图中无「环」存在， 是 AOV 网
2. 没有输出全部顶点：说明图中有「环」存在，不是 AOV 网

AOV（Activity On Vertex Network） ：一种 有向 无回路 的图。

求解方法：每次删除一个入度边个数为 0 的点，并刷新其他点的出度边个数