找到双连通组件的非递归算法

Question

是否有任何方法可以在非递归DFS中使用非递归DFS在无向图中找到双连通组件，以便它可以用于大图？

Answer 1

据我所知，它比一般的dfs更复杂一些。 一般尾递归解开循环相当不错。如果您有多个调用，但不要使用子例程结果，那么它的展开效果也不错。但是，如果你使用结果，goto/break或代码重复有点难以理解。

我已经得到了像这样有些丑陋的修改。说实话，我没有机会调试它，把它作为一般想法来制作你自己的代码。

import java.util.Stack; 

private void dfs2(Graph G, int u, int v) { 
    Stack<MyStackFrame> stack = new Stack<>(); 

    int children; 
    int wi = -1; 
    int w; 

    do { 
     if (wi < 0) { //start dfs 
      children = 0; 
      pre[v] = cnt++; 
      low[v] = pre[v]; 
      for (wi = 0; wi < G.adj(v).length; wi++) { 
       w = G.adj(v)[wi]; 
       if (pre[w] == -1) { 
        children++; 
        stack.push(new MyStackFrame(children, wi, u, v)); 
        //dfs(G, v, w); 
        wi = -1; 
        u = v; 
        v = w; 
        break; 
       } 
       // update low number - ignore reverse of edge leading to v 
       else if (w != u) 
        low[v] = Math.min(low[v], pre[w]); 
      } 
      if (wi < 0) 
       break; 
      // root of DFS is an articulation point if it has more than 1 child 
      if (u == v && children > 1) 
       articulation[v] = true; 
     } 
     else { // continue dfs 
      MyStackFrame stackFrame = stack.pop(); 
      u = stackFrame.u; 
      v = stackFrame.v; 
      children = stackFrame.children; 
      wi = stackFrame.wi; 
      w = G.adj(v)[wi]; 

      // update low number 
      low[v] = Math.min(low[v], low[w]); 

      // non-root of DFS is an articulation point if low[w] >= pre[v] 
      if (low[w] >= pre[v] && u != v) 
       articulation[v] = true; 
      wi++; 

      for (; wi < G.adj(v).length; wi++) { 
       w = G.adj(v)[wi]; 
       if (pre[w] == -1) { 
        children++; 
        stack.push(new MyStackFrame(children, wi, u, v)); 
        //dfs(G, v, w); 
        wi = -1; 
        u = v; 
        v = w; 
        break; 
       } 
       // update low number - ignore reverse of edge leading to v 
       else if (w != u) 
        low[v] = Math.min(low[v], pre[w]); 
      } 
      if (wi < 0) 
       break; 

      // root of DFS is an articulation point if it has more than 1 child 
      if (u == v && children > 1) 
       articulation[v] = true; 
     } 
    } while (!stack.empty());  
}