开始慢慢感受到这门课有多难了。。。
参考书：算法概论
L5-L7 是图论的开始。
L5
L5 介绍联通图的连通性
通过 DFS 进行遍历。
（1）加入计数，记录不同联通图的索引。
（2）加入 pre[v],post[v] 记录节点开始和结束的时间
对于有向图：
可以通过 pre,post 的节点顺序，判断边的类型。后面会经常用这个特性。
L6
DAG
DAG(Direct acyclic graph) is a digraph without no cycles.
如何判断是否是 DAG？
run DFS on G and output "DAG" if DFS reveeals no backedges.
这里用到了上一讲的回边判断。
强连通部件
定义：
有向图中的两个顶点 u,v。如果 u->v,v->u 各有一条路径，则称 u,v 是（强）联通的。
这一联通关系将顶点集合 V 划分成一系列分离集，称这些分离集为强连通部件
性质：每个有向图的强连通部件都是一个有向无环图。
关于强连通部件核心性质：
如果 C 和 C'是强连通部件，同时从 C 中的一个顶点到 C'的一个顶点存在一条边，则 C 中的 POST 最大值要大于 C'的最大值。
具体算法：
1.在图 GR（将所有边反向）上运行深度优先搜索。
2.在 G（原图）上运行图连通部件算法，按照 GR 得到的 POST 降序逐个获取。
可以参考理解强连通分量的 Tarjan 算法
https://www.cnblogs.com/yanyiming10243247/p/9294160.html
L7
最短路径
Dijkstia 算法（所有的边 weights>=0）O((|V|+|E|) log|V|)
Bellman-Fold 对所有边进行迭代 (没有 weights 为负数的环) O(|V||E|)，如果连续迭代没有改变，可以提前结束，并不一定需要迭代 |V| 次。