目录

Section-4 Connectivity 第4节 连通 - Gabow - Gabow算法

优质
小牛编辑
136浏览
2023-12-01

Gabow算法


问题:

用Gabow算法求有向图(G)的强连通分支。


解法:

Gabow算法是Tarjan算法一个变种,区别在于low值(详见)的处理方式,Gabow算法分为(2)个步骤:


((1))对图(G)中的所有节点进行深度优先搜索,计算每个遍历到的节点的(low)值,并将其压入栈(Stack)中;


((2))依次从栈(Stack)中取出每个节点,并放入初始为空的集合(S)中。对于刚刚进入集合的节点(i),若该节点为强连通分支的根节点,则当前集合(S)中的所有节点属于一个强连通分支。将它们全部取出作为一个强连通分支,将集合(S)清空,然后继续从栈(Stack)中取出节点,重复该操作。


Tarjan算法在节点数量为(N)的有向图上的时间复杂度为(O(N))。