UC知道“强连通分支算法”相关证明
来源：百度知道 编辑：UC知道 时间：2024/06/01 12:10:55
证明：在强连通分支算法中，选择任何顶点做起始点来执行深度优先搜索遍历，得到的强连通分支的解相同。
下面是强连通分支算法哦~：
1）对G进行深度优先搜索并按递归调用完成的先后顺序对各顶点后续遍历编号；
2）改变G的每条边的方向，构造出新的有向图Gr
3）按1）中的确定的顶点编号，从编号最大的顶点开始对Gr进行深度优先搜索。如果搜索的过程中没有访问遍Gr的所有顶点，则从未被访问过的顶点中选取编号最大的顶点，并从此顶点开始继续做深度优先搜索；
4）在最后得到的Gr的深度优先生成森林中，每棵树上的顶点组成G的一个强连通分支。
正好遇到这道题，希望有人能答复啊~ 谢谢了~
下面是强连通分支算法哦~：
1）对G进行深度优先搜索并按递归调用完成的先后顺序对各顶点后续遍历编号；
2）改变G的每条边的方向，构造出新的有向图Gr
3）按1）中的确定的顶点编号，从编号最大的顶点开始对Gr进行深度优先搜索。如果搜索的过程中没有访问遍Gr的所有顶点，则从未被访问过的顶点中选取编号最大的顶点，并从此顶点开始继续做深度优先搜索；
4）在最后得到的Gr的深度优先生成森林中，每棵树上的顶点组成G的一个强连通分支。
正好遇到这道题，希望有人能答复啊~ 谢谢了~
首先,这个算法求出的是一个有向图最大强连通子图.一个图的最大强连通子图只有一个解集(这没什么疑问吧).
那我只好理解为你要问这个算法如何求出的这个最大强连通子图（C）的解集.
首先改变边方向应该好理解,它能导出一个C。因为一个C里面的点在边改变后还是到能在一次深搜搜到的。唯一问题，如何保证不会搜出不是C的点。
这样的点有两种情况：在原图中这个点可以到达这个C但无法通过这个C到达它本身；可以通过C到达，但无法到达C。
第1种情况，这个点的编号肯定比C大，边变向后，就会先搜这个点，而且不会搜到C。
第2中情况雷同。
建议楼主在实践中采用求最早祖先的方法求最大强连通。方法也比较好理解，代码也短 ，只用一遍深搜就行。
希望楼主看完我的回答有所收益
关注中