反復DFSのエッジ分類

Question

エッジは、ノードを未訪問、発見、または終了（または、白、灰色、黒）にラベル付けする再帰的DFSを使用して、3つのカテゴリ（バックエッジ、ツリー/フォワードエッジ、クロスエッジ）に従って分類できます。

アルゴリズムの反復バージョン（Depth-First Search参照）を使用してエッジを分類することはできますか？

procedure DFS-iterative(G,v): 
2  let S be a stack 
3  S.push(v) 
4  while S is not empty 
5   v = S.pop() 
6   if v is not labeled as discovered: 
7    label v as discovered 
8    for all edges from v to w in G.adjacentEdges(v) do 
9     S.push(w) 

このバージョンでは、未訪問の2つのカテゴリのみが使用されています。すべての隣接ノードがスタックにプッシュされた後にノードを終了としてマークできましたが、期待される結果は得られませんでした。

EDIT（Clarification）：問題は、前述のDFSの反復バージョンを修正して、ツリー/フォワードエッジ、クロスエッジ、バックエッジとしてエッジを分類することです。ノードラベル/色を利用していますか？

Answer 1

再帰バージョンで作業しているとします。次のようにそれを変更することができる：それは未発見である頂点につながる場合

• エッジがツリーエッジである：

  DFS(G,v): 
      v.discovered = True 
      for all edges from v to w in G.adjacentEdges(v) do 
      if not w.discovered then 
       recursively call DFS(G,w) 
      v.finished = True 
  

  bracketingのアイデアを使用して、よくすることが知られています。

• エッジは、それが発見され、エッジが他のクロスまたは前縁である

• 終了していない頂点につながる場合後方エッジです。

ここで唯一の問題は反復的にすることです。唯一の違いは、以前は再帰が行ったことを操作する必要があることです。各頂点がnumActiveChildrenが0に設定され、parentがNilに設定されているとします。見ることができるの反復バージョンは、次のとおりです。これに

DFS-iterative(G,v): 
    let S be a stack 
    S.push(v) 
    while S is not empty do 
     v = S.pop() 
     if not v.discovered do 
      v.discovered = True 
      for all edges from v to w in G.adjacentEdges(v) do 
       if w.discovered do 
        w.parent.numActiveChildren = w.parent.numActiveChildren - 1 
       v.numActiveChildren = v.numActiveChildren + 1 
       w.parent = v 
       S.push(w) 

      while v != Nil and v.numActiveChildren = 0 do 
       v.finished = True 
       v = v.parent 
       if v != Nil do 
        v.numActiveChildren = v.numActiveChildren - 1 

Answer 2

私のソリューションは、スタックと、「現在の子」のポインタを使用して再帰をシミュレートすることです。

標準のDFSスタックからノードを覗くと、現在の子ポインタがこのノードの隣接リストの末尾を指しているかどうかがチェックされます。そうであれば、このノードが終了します。そうでなければ、現在の子ポインタを更新せずに、この子ノード（適格な場合）をDFSスタックにプッシュします。これにより、後でこの子に対して後処理を行うことができます。

例として、10199 - Tourist Guide from UVa Judgeを参考にしてください。基本的には、エッジ分類に決定的に依存する関節点を見つけるように求められます。 Recursive Solutionから

：

void CutVertexFinder::DFS(int root) { 
    for (auto&& child : graph[root]) { 
    if (child == parent[root]) continue; 

    if (parent[child] == -1) { 
     // Tree edge 
     parent[child] = root; 
     entry[child] = time++; 
     farthest_ancestor[child] = child; 

     num_children[root]++; 
     DFS(child); 

     if (entry[farthest_ancestor[child]] < entry[farthest_ancestor[root]]) { 
     farthest_ancestor[root] = farthest_ancestor[child]; 
     } 
    } else if (entry[child] < entry[root]) { 
     // Back edge 
     if (entry[child] < entry[farthest_ancestor[root]]) { 
     farthest_ancestor[root] = child; 
     } 
    } 
    } 
} 

Iterative Solutionから：

void CutVertexFinder::DFS(int root) { 
    std::vector<int> current_child_index(N, 0); 
    stack<int> S; 

    S.emplace(root); 
    while (!S.empty()) { 
    int node = S.top(); 

    const int child_index = current_child_index[node]; 
    if (child_index >= graph[node].size()) { 
     S.pop(); 
     continue; 
    } 

    int child = graph[node][child_index]; 
    if (child == parent[node]) { 
     current_child_index[node]++; 
     continue; 
    } 

    if (parent[child] == -1) { 
     parent[child] = node; 
     entry[child] = time++; 
     farthest_ancestor[child] = child; 

     num_children[node]++; 
     S.emplace(child); 
     continue; 
    } 

    if (parent[child] == node) { 
     if (entry[farthest_ancestor[child]] < entry[farthest_ancestor[node]]) { 
     farthest_ancestor[node] = farthest_ancestor[child]; 
     } 
    } else if (entry[child] < entry[node]) { 
     if (entry[child] < entry[farthest_ancestor[node]]) { 
     farthest_ancestor[node] = child; 
     } 
    } 
    current_child_index[node]++; 
    } 
} 

あなたが見ることができるように、反復解法は、おそらく過剰です。ここで

Answer 3

は、C++での私のソリューションです：

std::vector<bool> visited(number_of_nodes, false); 
std::vector<int> entry(number_of_nodes, 0); 
std::vector<int> exit(number_of_nodes, 0); 

// trace stack of ancestors 
std::vector<int> trace; 

int time = 1; 

// u is current node that moves around 
int u = nodes.front(); 
trace.push_back(u); 
visited[u] = true; 

// iterative DFS with entry and exit times 
while (!trace.empty()) { 
    bool found = false; 
    for (auto& v : neighbours_of(u)) { 
     if ((!visited[v]) && (!found)) { 
      found = true; // no blockage 
      u = v; 
      entry[u] = time++; 
      visited[u] = true; 
      trace.push_back(v); 
      break; 
     } 
    } 

    if (!found) { 
     trace.pop_back(); 
     exit[u] = time++; 
     u = trace.back(); 
    } 
} 

これは、DFSのためentryとexit回を取得します。これらの時間を使用して、hereのルールに従ってエッジを分類することができます。ルールは少し違っていますが、これをオンザフライでも実行できます。例えば、探索中にedge（u、v）に遭遇し、entry[v]が設定されているが、exit[v]がまだ設定されていない場合、（u、v）は後方エッジである。