强连通分量
我们认为有向图中的两个节点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正是在当前强连接组件中的所有节点耗尽时停止的。
实现代码
图一
测试一
图二
测试二
图三
测试三