ACM算法设计与竞赛II-3课.ppt

《ACM算法设计与竞赛II-3课.ppt》由会员分享，可在线阅读，更多相关《ACM算法设计与竞赛II-3课.ppt（10页珍藏版）》请在三一办公上搜索。

1、2023/11/7,ACM算法设计与竞赛II,1,第6章 图论算法,6.1 最短路径6.2 最小生成树6.3 最大匹配匈牙利算法6.4 最优权匹配问题6.5 割点、割边以及连通分量6.6 网络流6.7 实例分析6.8 小结,2023/11/7,ACM算法设计与竞赛II,2,6.5 割点、割边以及连通分量,6.5.1 理论基础6.5.2 求割点6.5.3 求强连通分量,2023/11/7,ACM算法设计与竞赛II,3,6.5.1 理论基础,1.时间戳dfni表示结点i是第dfni 个被访问到的结点。时间戳在遍历时能记录下许多有用的信息，所以是很多图算法的基础。,2023/11/7,ACM算法设计

2、与竞赛II,4,6.5.1 理论基础（续）,void dfs(v)dfnv=+times;/记录访问结点的时间戳 visitv=1;for 寻找一个v的相邻结点u if（visitu=0）then dfs(u);,2023/11/7,ACM算法设计与竞赛II,5,6.5.1 理论基础（续1）,2.割点割点：无向连通图中的割点指这样一个顶点，如果删除它，图就会被分割成至少两个分离的子图。割点也称为关节点（articulation point）。图6-3中顶点0、4、5、6、7和11为割点。割边（桥）：图中的割边（桥）是这样一条边，若删除它，则将连通图分离成两个断开的子图。,2023/11/7,A

3、CM算法设计与竞赛II,6,6.5.1 理论基础（续2）,3.强连通分量强连通图：在有向图G中,若对于任意两个顶点u,v,都存在从u到v的通路,也存在从v到u的通路,则称G为强连通图。强连通分量：有向图G的极大强连通子图称为G的强连通分量。例:图6-4。,2023/11/7,ACM算法设计与竞赛II,7,6.5.2 求割点,1.基本思想深度优先生成树树边,回边对树中任一顶点v而言,其孩子结点为在它之后搜索到的邻接点,而其双亲结点和由回边联结的祖先结点是在它之前搜索到的邻接点。,2023/11/7,ACM算法设计与竞赛II,8,6.5.2 求割点（续）,两类割点的特性：（1）若生成树的根有两棵或

4、两棵以上的子树，则此根结点必为割点。（2）若生成树中某个非叶结点v，其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边，则v为割点。,2023/11/7,ACM算法设计与竞赛II,9,6.5.2 求割点（续1）,定义：low(v)=mindfnv,loww,dfnk|w是顶点v在深度优先生成树上的孩子结点；k是顶点v在深度优先生成树上由回边联结的祖先结点。若对于某个顶点v，存在孩子结点w且low(w)=dfnv,则该顶点v必为割点。因为当w是v的孩子结点时，low(w)=dfnv,表明w及其子孙均无指向v的祖先的回边。,2023/11/7,ACM算法设计与竞赛II,10,6.5.2 求割点（续2）,2.样例代码articul.cpp,