0

在Tarjan 算法中，有两个索引数组，一个按节点被发现的顺序连续编号。另一个表示从v到v的子树可以到达的最小索引，这是算法的伪代码

    tarjan(u)
{
    DFN[u]=Low[u]=++Index                      
    Stack.push(u)                            
    for each (u, v) in E                    
        if (v is not visted)              
            tarjan(v)                
            Low[u] = min(Low[u], Low[v])
        else if (v in S)                  
            Low[u] = min(Low[u], DFN[v])
    if (DFN[u] == Low[u])                      
        repeat
            v = S.pop                  
            print v
        until (u== v)
}

但我认为可以删除低数组，算法更改为

tarjan(u)
{
    if(DFN[u]) // assume all elements in DFN is initialized to 0
        return DFN[u]
    DFN[u]=++Index                      
    Stack.push(u)      
    res = DFN[u]                     
    for each (u, v) in E                                          
        res = min(res, tarjan(v))
    if (DFN[u] == res)                      
        repeat
            v = S.pop                  
            print v
        until (u== v)
    return res
}

我对小图做了一些测试，结果与标准 tarjan 相同。但我不确定它是否能成功地在各种图中找到强连通分量。这个算法是正确的还是只能通过弱测试用例。

4

1 回答 1

1

我同意 MrSmith42 的观点，即详尽列举小例子是获得信心的好方法。

但是，即使添加了 missing return res，我认为您的算法仍然不正确。两个顶点图，2 → 1。如果我们遍历 1 再遍历 2，resfor 2 的值为 1，导致 {2} 作为强分量被遗漏。

于 2021-05-18T17:02:09.120 回答