有向图的强连通分量怎么求啊?
百科上说要用Tarjan算法 http://baike.baidu.com/view/6156928.htm
Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
定义DFN(u)为节点u搜索的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。
接下来是对算法流程的演示。
从节点1开始DFS,把遍历到的节点加入栈中。搜索到节点u=6时,DFN[6]=LOW[6],找到了一个强连通分量。退栈到u=v为止,{6}为一个强连通分量。
我去,到这一步我就不大看得懂了,另外,他说的“时间戳”、“次序号”又该怎么理解呢? 图论算法? 算法 强连通? Tarjan
[解决办法]
看这个图肯定看不懂的。以时间戳为基础的那一票算法初学的时候一定要画DFS树,先只画DFS树上的边,然后再加back edge/cross edge/forward edge。
[解决办法]
这个图的真就是个垃圾,自己肯定没理解
时间戳:名字叫的很古怪,就是DFS遍历节点的过程中,按发现节点的先后顺序进行编号,从1到N
DFS遍历过程得到一棵树,倒是在纸上把这个树画出来,不画出来就没法理解了
画完树之后,把树上没体现出来的边也加上去(用另一种颜色)
LOW(u)的定义:u是一个节点,也可以理解为以u为根的子树,LOW(u)=MIN(从子树u出发的所有回边 的宿节点的时间戳)