Tarjan算法的非递归版本

Question

我有以下（递归）实现Tarjan算法以在图中查找强连通分量，它运行良好：

public class StronglyConnectedComponents
{
    public static List<List<int>> Search(Graph graph)
    {
        StronglyConnectedComponents scc = new StronglyConnectedComponents();
        return scc.Tarjan(graph);
    }

    private int preCount;
    private int[] low;
    private bool[] visited;
    private Graph graph;
    private List<List<int>> stronglyConnectedComponents = new List<List<int>>();
    private Stack<int> stack = new Stack<int>();

    public List<List<int>> Tarjan(Graph graph)
    {
        this.graph = graph;
        low = new int[graph.VertexCount];
        visited = new bool[graph.VertexCount];

        for (int v = 0; v < graph.VertexCount; v++) if (!visited[v]) DFS(v);

        return stronglyConnectedComponents;
    }

    public void DFS(int v)
    {
        low[v] = preCount++;
        visited[v] = true;
        stack.Push(v);
        int min = low[v];
        int edgeCount = graph.OutgoingEdgeCount(v);
        for (int i = 0; i < edgeCount; i++)
        {
            var edge = graph.OutgoingEdge(v, i);
            int target = edge.Target;

            if (!visited[target]) DFS(target);
            if (low[target] < min) min = low[target];
        }

        if (min < low[v])
        {
            low[v] = min;
            return;
        }

        List<int> component = new List<int>();

        int w;
        do
        {
            w = stack.Pop();
            component.Add(w);
            low[w] = graph.VertexCount;
        } while (w != v);
        stronglyConnectedComponents.Add(component);
    }
}

但是在大型图上，递归版本显然会抛出StackOverflowException异常。因此，我想使算法非递归。

我尝试用以下（非递归）函数替换DFS函数，但是算法不再起作用了。有人可以帮忙吗？

private void DFS2(int vertex)
{
    bool[] visited = new bool[graph.VertexCount];
    Stack<int> stack = new Stack<int>();
    stack.Push(vertex);
    int min = low[vertex];

    while (stack.Count > 0)
    {
        int v = stack.Pop();
        if (visited[v]) continue;
        visited[v] = true;

        int edgeCount = graph.OutgoingEdgeCount(v);
        for (int i = 0; i < edgeCount; i++)
        {
            int target = graph.OutgoingEdge(v, i).Target;
            stack.Push(target);
            if (low[target] < min) min = low[target];
        }
    }

    if (min < low[vertex])
    {
        low[vertex] = min;
        return;
    }

    List<int> component = new List<int>();

    int w;
    do
    {
        w = stack.Pop();
        component.Add(w);
        low[w] = graph.VertexCount;
    } while (w != vertex);
    stronglyConnectedComponents.Add(component);
}

以下代码展示了测试：

public void CanFindStronglyConnectedComponents()
{
    Graph graph = new Graph(8);
    graph.AddEdge(0, 1);
    graph.AddEdge(1, 2);
    graph.AddEdge(2, 3);
    graph.AddEdge(3, 2);
    graph.AddEdge(3, 7);
    graph.AddEdge(7, 3);
    graph.AddEdge(2, 6);
    graph.AddEdge(7, 6);
    graph.AddEdge(5, 6);
    graph.AddEdge(6, 5);
    graph.AddEdge(1, 5);
    graph.AddEdge(4, 5);
    graph.AddEdge(4, 0);
    graph.AddEdge(1, 4);

    var scc = StronglyConnectedComponents.Search(graph);
    Assert.AreEqual(3, scc.Count);
    Assert.IsTrue(SetsEqual(Set(5, 6), scc[0]));
    Assert.IsTrue(SetsEqual(Set(7, 3, 2), scc[1]));
    Assert.IsTrue(SetsEqual(Set(4, 1, 0), scc[2]));
}

private IEnumerable<int> Set(params int[] set) => set;

private bool SetsEqual(IEnumerable<int> set1, IEnumerable<int> set2)
{
    if (set1.Count() != set2.Count()) return false;
    return set1.Intersect(set2).Count() == set1.Count();
}

- user2033412

---

也许你应该将这个问题转到http://codereview.stackexchange.com/。 - aloisdg

请查看此链接：http://rextester.com/discussion/YUYX6886/BFS-DFS-stack-vs-recursive。 - AlanderC

在 Code Review 上交叉发布，但很快就吸引了 @aloisdg 的关闭票。 - Mast

Answer 1

这是原始的递归实现的直接非递归翻译（假设它正确）：

public static List<List<int>> Search(Graph graph)
{
    var stronglyConnectedComponents = new List<List<int>>();

    int preCount = 0;
    var low = new int[graph.VertexCount];
    var visited = new bool[graph.VertexCount];
    var stack = new Stack<int>();

    var minStack = new Stack<int>();
    var enumeratorStack = new Stack<IEnumerator<int>>();
    var enumerator = Enumerable.Range(0, graph.VertexCount).GetEnumerator();
    while (true)
    {
        if (enumerator.MoveNext())
        {
            int v = enumerator.Current;
            if (!visited[v])
            {
                low[v] = preCount++;
                visited[v] = true;
                stack.Push(v);
                int min = low[v];
                // Level down
                minStack.Push(min);
                enumeratorStack.Push(enumerator);
                enumerator = Enumerable.Range(0, graph.OutgoingEdgeCount(v))
                    .Select(i => graph.OutgoingEdge(v, i).Target)
                    .GetEnumerator();
            }
            else if (minStack.Count > 0)
            {
                int min = minStack.Pop();
                if (low[v] < min) min = low[v];
                minStack.Push(min);
            }
        }
        else
        {
            // Level up
            if (enumeratorStack.Count == 0) break;

            enumerator = enumeratorStack.Pop();
            int v = enumerator.Current;
            int min = minStack.Pop();

            if (min < low[v])
            {
                low[v] = min;
            }
            else
            {
                List<int> component = new List<int>();

                int w;
                do
                {
                    w = stack.Pop();
                    component.Add(w);
                    low[w] = graph.VertexCount;
                } while (w != v);
                stronglyConnectedComponents.Add(component);
            }

            if (minStack.Count > 0)
            {
                min = minStack.Pop();
                if (low[v] < min) min = low[v];
                minStack.Push(min);
            }
        }
    }
    return stronglyConnectedComponents;
}

通常情况下，对于这种直接翻译，您需要使用显式堆栈来存储需要在递归调用后恢复的状态。在本例中，它是级别顶点枚举器和min变量。

请注意，现有的stack变量不能使用，因为虽然处理顶点被推入其中，但并不总是在退出时弹出（递归实现中的return行），这是该算法的特定要求。

- Ivan Stoev

---

谢谢你的帮助！不幸的是，代码无法运行，它输出了以下强连通分量[[5,6],[7,3,2],[4,1],[0]]。 - user2033412

期望的输出是什么（或者递归实现会产生什么结果）？不幸的是，由于缺少某些相关类和测试数据，我无法进行测试。 - Ivan Stoev

我刚试了你更新后的代码，它仍然产生相同（错误）的输出。正确的输出应该是[[5,6],[7,3,2],[4,1,0]]。 - user2033412

这次编辑不好，我已经恢复了。现在试试看。看起来我错过了if (low[target] < min) min = low[target];部分在调用DFS(target)之后执行的情况。 - Ivan Stoev

Answer 2

以下是我为Codeforces 427C实现的Python版本，因为他们不支持增加Python堆栈大小。

该代码使用一个额外的调用堆栈，其中包含指向当前节点的指针以及下一个要访问的子节点。

实际算法紧密遵循维基百科上的伪代码。

N = # number of vertices
es = # list of edges, [(0,1), (2,4), ...]

class Node:
    def __init__(self, name):
        self.name = name
        self.index = None
        self.lowlink = None
        self.adj = []
        self.on_stack = False

vs = [Node(i) for i in range(N)]
for v, w in es:
    vs[v].adj.append(vs[w])

i = 0
stack = []
call_stack = []
comps = []
for v in vs:
    if v.index is None:
        call_stack.append((v,0))
        while call_stack:
            v, pi = call_stack.pop()
            # If this is first time we see v
            if pi == 0:
                v.index = i
                v.lowlink = i
                i += 1
                stack.append(v)
                v.on_stack = True
            # If we just recursed on something
            if pi > 0:
                prev = v.adj[pi-1]
                v.lowlink = min(v.lowlink, prev.lowlink)
            # Find the next thing to recurse on
            while pi < len(v.adj) and v.adj[pi].index is not None:
                w = v.adj[pi]
                if w.on_stack:
                    v.lowlink = min(v.lowlink, w.index)
                pi += 1
            # If we found something with index=None, recurse
            if pi < len(v.adj):
                w = v.adj[pi]
                call_stack.append((v,pi+1))
                call_stack.append((w,0))
                continue
            # If v is the root of a connected component
            if v.lowlink == v.index:
                comp = []
                while True:
                    w = stack.pop()
                    w.on_stack = False
                    comp.append(w.name)
                    if w is v:
                        break
                comps.append(comp)

另外，按照"简化版" Tarjan算法的方式，我们可以进行以下翻译：

def scc2(graph):
    result = []
    stack = []
    low = {}
    call_stack = []
    for v in graph:
        call_stack.append((v, 0, len(low)))
        while call_stack:
            v, pi, num = call_stack.pop()
            if pi == 0:
                if v in low: continue
                low[v] = num
                stack.append(v)
            if pi > 0:
                low[v] = min(low[v], low[graph[v][pi-1]])
            if pi < len(graph[v]):
                call_stack.append((v, pi+1, num))
                call_stack.append((graph[v][pi], 0, len(low)))
                continue
            if num == low[v]:
                comp = []
                while True:
                    comp.append(stack.pop())
                    low[comp[-1]] = len(graph)
                    if comp[-1] == v: break
                result.append(comp)
    return result

- Thomas Ahle