Some icons made by Freepik from www.flaticon.com is licensed by CC 3.0 BY
Some icons made by Icons8
所有课程资源,包括课程内容、图片、附件、代码等均为用户上传分享,平台仅提供存储和展示服务,如有侵权,请邮件联系 support@python123.org,告知网页链接和侵权证据,平台将及时删除
未得到原作者授权,禁止转载本站任何内容
All Rights Reserved.
Python123 是专注于为中国高等院校教学 Python 语言的而开发的一款学习工具网站。集 Python123 高等教师课题教学、日常考试、习题训练、计算生态以及计算机等级考试 Python 部分的指导模拟网站。Python123 还汇聚全国计算机教育名师的 Python 公开课免费视频教程,共同缔造 Python 这门编程语言的全新教学模式。
18年11月20日 · 史二美—北京理工大学 606 阅读
我们认为有向图中的两个节点U和V属于同一强连通分量[SCC],如果存在从U到V的路径和从V到U的路径。
找到所有SCC的算法是惊人的简单和相当聪明。
(1)在图G上运行深度优先搜索[dfs]并记住DFS从节点完成搜索的时间
(2)通过倒转G中的边方向创建图G‘
(3)按降时给出的顺序在图G‘上运行DFS
(4)步骤3中可从节点U到达的所有节点形成单个SCC
![]() |
看照片。图G包含编号为1,2,3的SCC。当我们将G中的每个分量收缩成一个节点时,我们得到一个新的图T,它是有向的,无圈的。当DFS从节点U中搜索G时,当U的组件中的所有节点都耗尽时(如果可能从U中到达另一个SCC),则停止。如果你看图T,组件的完成时间是:时间(1)=3,时间(2)=2,时间(3)=1。然后,第二个DFS被迫以1,2,3的顺序运行在一个反图G‘/T’上。这一次,DFS正是在当前强连接组件中的所有节点耗尽时停止的。
![]() |
![]() |
![]() |
![]() |
About
Some icons made by Freepik from www.flaticon.com is licensed by CC 3.0 BY
Some icons made by Icons8
所有课程资源,包括课程内容、图片、附件、代码等均为用户上传分享,平台仅提供存储和展示服务,如有侵权,请邮件联系 support@python123.org,告知网页链接和侵权证据,平台将及时删除
未得到原作者授权,禁止转载本站任何内容
All Rights Reserved.
发送反馈
您可以向 support@python123.org 发送反馈邮件,我们会回复所有邮件
如果您在使用过程中发生异常,例如无法保存、无法提交、得分为 0 或者其它错误,
请将您遇到问题的 课程、单元、习题 信息以及您的联系方式发送到邮箱,我们会联系您进行处理
Tip: 您对问题的描述越清晰,我们的处理速度通常也越快
Python123 Version ( 更新)
版权声明联系我们: supportpython123.org
Python123 Development Team, All rights reserved.
苏ICP备16066778号-1
微信公众号
兼容性提示
您正在使用的 IE 浏览器,或部分浏览器的 IE 模式 访问本站
现阶段我们还无法提供对 IE 的完整支持
如果继续浏览可能遇到 排版混乱、部分功能无法正常使用 等错误
建议您使用 Chrome、Edge、Firefox、Safari 等现代浏览器访问