c# - 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();
}

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 行) ，这是该算法的特定要求。