中科新闻网深圳永贵技术有限公司:[图论]DFS求有向图强连通分量算法的正确性
来源：百度文库 编辑：中科新闻网 时间：2024/04/30 00:51:55
有以下算法：
（1）在有向图G上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成(即退出DFS函数)的顺序将顶点排列起来。此时需对利用深度优先搜索，求有向图G的强连通分支的算法步骤：
1）对G进行深度优先搜索并按递归调用完成的先后顺序对各顶点编号；
2）改变G的每条边的方向，构造出新的有向图Gr
3）按1）中的确定的顶点编号，从编号最大的顶点开始对Gr进行深度优先搜索。如果搜索的过程中没有访问遍Gr的所有顶点，则从未被访问过的顶点中选取编号最大的顶点，并从此顶点开始继续做深度优先搜索；
4）在最后得到的Gr的深度优先生成森林中，每棵树上的顶点组成G的一个强连通分支。
在数据结构上看到的，我对这个算法的原理不是很理解，请各位大牛不吝赐教，越详细越好
（1）在有向图G上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成(即退出DFS函数)的顺序将顶点排列起来。此时需对利用深度优先搜索，求有向图G的强连通分支的算法步骤：
1）对G进行深度优先搜索并按递归调用完成的先后顺序对各顶点编号；
2）改变G的每条边的方向，构造出新的有向图Gr
3）按1）中的确定的顶点编号，从编号最大的顶点开始对Gr进行深度优先搜索。如果搜索的过程中没有访问遍Gr的所有顶点，则从未被访问过的顶点中选取编号最大的顶点，并从此顶点开始继续做深度优先搜索；
4）在最后得到的Gr的深度优先生成森林中，每棵树上的顶点组成G的一个强连通分支。
在数据结构上看到的，我对这个算法的原理不是很理解，请各位大牛不吝赐教，越详细越好
详情请见《数据结构》第三版