Классификация края в итеративном режиме 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) 

В этой версии используются только две категории: нераскрытые и обнаруженные. Мы могли бы отметить, что узел завершен после того, как все соседние узлы были перенесены в стек, но это не даст ожидаемого результата.

EDIT (уточнение): Вопрос в том, можем ли мы изменить итеративную версию 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 раз для ДПП. Эти края можно классифицировать в соответствии с правилами, указанными here, используя эти времена. Вы можете сделать это и на лету, хотя правила немного разные. Например, во время поиска, если мы встречаем ребро (u, v) и entry[v], установлено, но exit[v] еще не установлено, тогда (u, v) является обратным краем.