图论-刘汝佳.ppt

《图论-刘汝佳.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一些图论算法刘汝佳目录DFS相关算法二分图相关算法网络流相关算法最小树形图DFS相关算法基本应用找连通分量二分图判定无向图的连通性有向图的连通性时间戳和边分类时间初始化为0，最大值为2

2、E

3、。数值本身无意义，但大小关系有意义voidPREVISIT(intu){pre[u]=++dfs_clock;}voidPOSTVISIT(intu){post[u]=++dfs_clock;}无向图：只有树边和反向边无向连通图的割顶DFS森林一定只有一棵树。树根是不是割顶呢？不难发现，当且仅当它有两个或更多的儿子时，它才是割顶—

4、—无向图只有树边和反向边，不存在跨越两棵子树的边。对于其他点，情况就要复杂一些。我们有下面的定理：定理：在无向连通图G的DFS树中，非根结点u是G的割顶当且仅当u存在一个儿子w，使得w及其所有后代都没有反向边连回u的祖先（连回u不算）。定理的证明u存在一个儿子w，使得w及其所有后代都没有反向边连回u的祖先（连回u不算）。为了方便起见，我们设low(u)为u及其后代所能连回的最早的祖先的pre值，则定理中的条件就可以简写成：结点u存在一个儿子w，使得low(w)>=pre(u)。若low(w)>pre(u)，即w最多只

5、能连回自己，则只需删除(u,w)一条边就可以让图G非连通了。满足这个条件的边称为桥（bridge）low函数本身的计算voiddfs(intu,intfa){//u的父亲结点是fa，初次调用fa=-1low[u]=pre[u]=++dfs_clock;//初始化low(u)intd=G[u].size();for(inti=0;i

6、n(low[u],low[w]);//用后代的low函数更新}elseif(w!=fa)low[u]=min(low[u],pre[w]);//用反向边更新}}双连通与边-双连通如果一个无向连通图没有割顶，称它是点-双连通的，一般简称双连通（biconnected）；如果没有桥，称它是边-双连通（edge-biconnected）的。点-双连通的等价条件：任意两点存在两条“点不重复”的路径。这个要求等价于任意两条边都在同一个简单环中，因此内部无割顶。边-双连通的等价条件：任意两点存在两条“边不重复”的路径。这个要求要

7、低一点，只需要每条边都至少在一个简单环中，因此所有边都不是桥。点/边-双连通分量下图有两个点-双连通分量：{1,2,3}和{3,4,5}，但只有一个边-双连通分量：{1,2,3,4,5}。算法边-双连分量：两步走，先求出所有的桥，然后再做一次dfs染色。因为边-双连通分量是没有公共顶点的，所以只要在第二次dfs的时候保证不经过桥即可。点-双连通分量：Tarjan算法（见后）voiddfs(intu,intfa){low[u]=pre[u]=++dfs_clock;intd=G[u].size();for(inti=0

8、;i=pre[u]){//u是割顶或者根，意味着一个bcc的终止++bcc_cnt;printf("BCC%d,containing(%d,%d):",bcc_cnt,u,w

9、);paire;do{e=S.top();S.pop();printf("%d%d",e.first,e.second);}while(e!=mp(u,w));}}elseif(w!=fa)low[u]=min(low[u],pre[w]);}}有向图的强连通分量理想情况：依次从I,C,D…出发DFS，则每次DFS恰好得到一个SCCKosaraju算法执行两次DFS，其中第一次DFS得到了关于各个SCC拓扑顺序的有关信息，而第二次DFS按照这个拓扑顺序的逆序进行DFS，从而把每个SCC分开。第一

10、步：对G进行普通的DFS，把各个结点按照访问结束时间从后往前的顺序放入列表list中。第二步：计算G的转置GT（即把所有有向边(u,v)变为有向边(v,u)）第三步：对GT进行DFS，其中主循环中按下标从小到大的顺序依次考虑list中的各个结点，则每次dfs将会得到一个不同的SCC。圆桌骑士每次圆桌会议由至少3个骑士参加，骑士的数目必须为奇数，