迭代DFS中的邊緣分類

Question

使用將節點標記爲未訪問，已發現或已完成（或白色，灰色，黑色）的遞歸DFS，可以根據三類（後緣，樹/前緣，交叉邊緣）對邊緣進行分類。

我們是否也可以使用算法的迭代版本對比邊緣（參見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) 

該版本只使用兩個類別，未訪問和發現。在所有相鄰節點被推入堆棧之後，我們可以將節點標記爲完成，但它不會給出預期的結果。 （澄清）：問題是，我們可以修改上面給出的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 - 從UVA法官的旅遊指南。它基本上要求我們找到關鍵點，這些關鍵點取決於邊緣分類。

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

這將得到entry和exit時間爲DFS。邊緣可以根據使用這些時間發佈的規則here進行分類。儘管規則有些不同，但您也可以在飛行中執行此操作。例如，在搜索期間，如果我們遇到邊（u，v），並且entry[v]被設置，但是exit[v]尚未設置，則（u，v）是後向邊。