1.暴力算法 2.Tarjan算法 3.RMQ求LCA
暴力求LCA
So easy
tarjan
RMQ求LCA
未完待续
最小生成树
1.prim 2. Kruskal
Prim
So easy
Kruskal
So easy
最小属性图
朱刘算法 /sdj222555/article/details/7459738 最好理解，至少会使用模板
LCA
即最近公共祖先
CUGB图论入.最短路 2.树相关 3.拓扑排序 4. 二分图相关 5.图的连通性 6.2-SAT 7.网络流
邻接表
1.使用vector代替邻 接表 2.手写邻接表 见右图
最短路
1.dijkstra 2.spfa
dijkstra
Dijkstra优化
使用堆可以优化dijkstra 一般可使用priority_queue 必须掌握！！！
堆优化的dijkstra
spfa
Spfa扩展
如题：每天,农夫John需要经过一些道路去检查牛棚 N里面的牛. 农场上有M(1<=M<=50,000)条双向 泥土 道路,编号为1..M. 道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N). John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从 P2_i 走到P１_i 他想更新一些路经来减少每天花在路 上的时间.具体地说,他想更新K (1 <= K <= 20)条路经， 将它们所须时间减为０．帮助FJ选择哪些路经需要 更新使得从１到N的时间尽量少.