ACM算法设计与竞赛II-3课.ppt_第1页
ACM算法设计与竞赛II-3课.ppt_第2页
ACM算法设计与竞赛II-3课.ppt_第3页
ACM算法设计与竞赛II-3课.ppt_第4页
ACM算法设计与竞赛II-3课.ppt_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

2019/8/4,ACM算法设计与竞赛II,1/66,第6章 图论算法,6.1 最短路径 6.2 最小生成树 6.3 最大匹配匈牙利算法 6.4 最优权匹配问题 6.5 割点、割边以及连通分量 6.6 网络流 6.7 实例分析 6.8 小结,2019/8/4,ACM算法设计与竞赛II,2/66,6.5 割点、割边以及连通分量,6.5.1 理论基础 6.5.2 求割点 6.5.3 求强连通分量,2019/8/4,ACM算法设计与竞赛II,3/66,6.5.1 理论基础,1. 时间戳 dfni表示结点i是第dfni 个被访问到的结点。 时间戳在遍历时能记录下许多有用的信息，所以是很多图算法的基础。,2019/8/4,ACM算法设计与竞赛II,4/66,6.5.1 理论基础（续）,void dfs(v) dfnv = +times; /记录访问结点的时间戳 visitv = 1; for 寻找一个v的相邻结点u if （visitu = 0）then dfs(u); ,2019/8/4,ACM算法设计与竞赛II,5/66,6.5.1 理论基础（续1）,2. 割点 割点：无向连通图中的割点指这样一个顶点，如果删除它，图就会被分割成至少两个分离的子图。 割点也称为关节点（articulation point）。 图6-3中顶点0、4、5、6、7和11为割点。 割边（桥）：图中的割边（桥）是这样一条边，若删除它，则将连通图分离成两个断开的子图。,2019/8/4,ACM算法设计与竞赛II,6/66,6.5.1 理论基础（续2）,3. 强连通分量 强连通图：在有向图G中,若对于任意两个顶点u,v,都存在从u到v的通路,也存在从v到u的通路,则称G为强连通图。 强连通分量：有向图G的极大强连通子图称为G的强连通分量。 例:图6-4。,2019/8/4,ACM算法设计与竞赛II,7/66,6.5.2 求割点,1. 基本思想 深度优先生成树 树边,回边 对树中任一顶点v而言,其孩子结点为在它之后搜索到的邻接点,而其双亲结点和由回边联结的祖先结点是在它之前搜索到的邻接点。,2019/8/4,ACM算法设计与竞赛II,8/66,6.5.2 求割点（续）,两类割点的特性： （1）若生成树的根有两棵或两棵以上的子树，则此根结点必为割点。 （2）若生成树中某个非叶结点v，其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边，则v为割点。,2019/8/4,ACM算法设计与竞赛II,9/66,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的祖先的回边
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论