图论已经入了好多次门了（乐），这里略去已经知道的经典算法，比如Dijsktra, floyed等，主要关注最大流问题。

树的杂七杂八#

无根树转有有根树，这个前面动态规划提到过，很简单，略。

表达式树#

这个问题数据结构课上大加强调，怎么生成一颗表达式树也已知其一，此处略。
这里讨论一下怎么找公共子树，即相同的子树。

找公共子树
一棵树中有很多子树，找出其中完全相同的子树，每棵公共子树应该尽可能大。

考虑编码的方法。目标是给每个节点编码，然后每个编码相同的节点，表示以这两个节点为根的子树是完全一样的。可以用状态 (node, left_num, right_num) 表示一棵以某一结点为根的子树，其中 node 是这个节点本来存的内容而非编号。
令 map(node)(left_num)(right_num) 映射节点node的编号。后序遍历整棵树，在确定某一个节点的编号时，先确定左儿子编号、右儿子编号，然后在map中查找 map(this_node)(left_num)(right_num) 是否已经存在，如果存在，就说明以此结点为根的子树和对应编号的节点子树完全相同，这个节点以此为编号。否则表示这可子树没有出现过，在map中添加并用一个新的编号。

最小生成树与 Kruskal、Prim#

Kruskal + 并查集的实现很简单，Prim也比较熟悉，这里略。
谈谈所谓动态最小生成树，即在边权产生变动的情况下的生成树的变化。
对于连续匀速变化的题目，最小生成树改变只发生在两条边的权重大小变得相等，并且恰好本来比较小的那一边在最小生成树中（较大的边不在），而接下来这条边要变得比较大。没有发生恰好两条边变得相等的时候，边排序不会改变，而恰好两条边变等，直觉上来说这两条边应该在原本的排序中相邻，只有这个相邻的顺序发生改变，它们前面的不变、后面的也不变，如果都不在，之后也会都不在；如果都在，之后也会都在；如果原本小的不在原本大的在，之后也不变；如果原本小的在原本大的不在，可能发生变化。 （这是对一道题目的分析。。）
在一些发生边权减小的情况，一些边的权值减小了，考虑Kruskal 的特点，权值不变并且原本没在最小生成树中的边，原本在它前面的边还在它前面，还可能插入一些边权减小了的边，所以原本没选上的边，边权不减小，更加不会被选上，可以优化掉这些边。

最短路问题#

也比较熟悉。主要补充一个考虑负权和有环的 Bellman-Ford 算法。

Dijkstra#

这个很熟悉，就是要编程回忆一下…
注意可以直接用 STL 的优先队列，对于结点可以重复压入优先队列中，然后每次从优先队列弹出一个节点，设置这个节点 done[i]=1，后面弹出节点，如果检测到 done[i]=1 表示已经完成，忽略它。

Floyed#

也比较熟悉，而且代码十分简练，如下：

G[n][n];    //类似邻接矩阵表示，对角线为0，没有边为很大的数。  
			//理解为不经过任何中间结点的最短路径距离  
for(int k=0; k<n; k++){  //经过了0...k的最短路径  
	for(int i=0; i<n; i++){  
		for(int j=0; j<n; j++){  
			if(G[i][k]+G[k][j]<G[i][j])  
				G[i][j]=G[i][k]+G[k][j];  
		}  
	}  
}  

Bellman-Ford#

有负权、有环。
如果有正环、零环，最短路径仍旧是没有环的路径，（删环要么有益要么无影响），如果有负环，没有最短路径。
n阶图无环路径最长也就n-1条边，为算法提供了基础。
和Dijsktra类似，从起点出发（先把起点入队），不断从 普通队列 中弹出一个点，如果从起自这个点的边到达另一点的最短距离小于另一点现有的最短距离，就更新这另一个点。如果这另一个点不在队列中，就入队，并这另一个点的 cnt[ ] 上+1，如果加到大于n，就说明有负环，到这个点的最短路无解。

最大网络流#

之前在《数据结构与算法分析》中了解，但已忘记（类似的情况还有强连通分支，等…）。这里聊做简述。

增广路算法#

每次从起点 s 到终点 t 找一条路径，这条路径叫增广路，路径中剩余容量 (当容量大于实际流量，容量-实际流量为最大剩余容量) 最小的为可补充流量，在沿途 各边的实际流量 中加上这补充流量，并在反向路径 中减掉这补充流量，在总最大流中加上这补充流量。一直到找不到增广路，算法结束。
实现技巧：

• 图的表示：边集 + 点上边的编号：edges[]存一系列边，G[i][j]表示从 i 到 j 的边在 edge 中的下标。
• 边数据结构保存：起点，终点，容量，实际流量。反向边的容量为0。存入 edges 的时候，将原有边与参量图的反向边同时存入，这样可以直接异或一个1找到反向边。
• 用BFS找增广路（不用“最”），普通增广路即可，找到一条到终点的路径即结束。用p数组存增广路中节点的“父亲”（上一个节点编号），用a[x] 存从s到 x 的路径中最小剩余容量是多少。找到增广路的标志是 a[t] 不为0.
• 一定将增广路中涉及的边加上剩余容量，反向边减去剩余容量（而不管是否在原图中存在）。一定将总最大容量加剩余容量
• 比较复杂。

最小割最大流#

割：把顶点分为两个集合S T，删除所有起于S中的点、终于T中点的边，为割。
定义割的容量为所有起于S、终于T的边的容量之和。
以S中一点为s，T中一点为终 t ，最大流小于等于割的容量。
当增广路算法结束的时候，没有从 s 到 t 的路径，此时从s能到达的点为S，t 能到达的点为 T，S到T的剩余容量为0（边全部满载），这样一定有上一段那个“小于等于”取等。
这样，增广路结束时，得到流量为最大流，得到割为最小割。

最小费用最大流#

改进搜索增广路的算法即可。如果全是正费用，可以 Dijkstra，否则Bellman-Ford。注意判断是否有这条边要用 容量>实际流量，而路径距离、权重用费用。

实践中，网络流问题一般用更高效的 Dinic 或者 ISAP 算法。

二分图匹配#

二分图：把顶点集分为两个集合，所有边恰好一个断点在一个集合，另一个断点在另一个集合。
匹配：两两没有公共点的边的子集。
二分图匹配，是给二分图（一般还会直接把两个顶点集给你），求匹配。
网络流在匹配问题中的意义在于，网络流约束中间结点流入=流出，如果容量全为1，如果有两个边有公共节点，这个节点流出只有一条容量为1的边，那么若其中一边选满了1，另一边一定不会被选到，保证了没有公共顶点。

无向无权图最大基数匹配#

无权二分图，求一个匹配，使得匹配上涉及的点尽可能多。
任选二分图中的一个顶点集为S，另一个为T，添加一个源s，s与S中所有点相连，容量全为1；新增终点 t，t 与T类似处理。将ST间所有边改为从S指向T，然后求最大流。
最后数数从s发出的边，满载（1）的边数为最大基数匹配匹配数。

无向带权图最大权完美匹配#

求匹配，所有顶点都匹配上，并且边权之和尽可能大。
类似上面最大基数匹配，添加 s,t, 然后以权值为费用，容量全部为1，求最小费用最大流（权值取反，化最大化为最小化）。
如果从s出发的边不是全部满载（1），完美匹配不存在，否则原图中所有满载的边为最大权完美匹配。