Итеративная DFS - где пометить узел как посещенный?

Question

Это моя реализация итерационных dfs, основанная на некоторых предложениях, которые я видел здесь, где отмечается, что узел отмечается как посещенный, как только он добавляется в стек.

Я рассмотрел некоторые другие реализации, такие как https://www.geeksforgeeks.org/iterative-depth-first-traversal/, где узел помечается как посещенный после его удаления из стека. Большинство реализаций, которые я видел, помечает его как посещенный после его удаления из стека. В чем преимущество такой реализации по сравнению с тем, что я сделал? В этой версии похоже, что вы все еще go просматриваете for l oop, даже если вы уже посетили текущий узел. В моей версии вы никогда не столкнетесь со случаем, когда for l oop выполняется для посещенного узла.

После дальнейшего просмотра моего текущего кода я вижу, что помечаю его как посещенный, прежде чем помещать его в стек. Будет ли правильный способ пометить его как посещенный после помещения в стек?

#include <iostream>


#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <stack>
using namespace std;

void dfs_iterative(const std::unordered_map<int, std::vector<int>> &adj_list, 
   const int source, const int target)
{
   if(source == target) return;
    unordered_set<int> visited;

   std::stack<int> st;

   st.emplace(source);
   visited.emplace(source);

   while(!st.empty())
   {
      auto head = st.top();
      st.pop();

      cout << head << endl;

      for(const auto &neighbor : adj_list.at(head)) 
      {
         if(visited.find(neighbor) == visited.end())
         {
            visited.emplace(neighbor);
            st.emplace(neighbor);
         }
      }
   }
}

int main( ) 
{ 
    unordered_map<int, vector<int>> adj_list;
    adj_list[0] = {1};
    adj_list[1] = {2,3};
    adj_list[2] = {3};
    adj_list[3] = {2};

    dfs_iterative(adj_list, 0, 11);
}

Answer 1

Ваш код на самом деле не поддерживает DFS. Для того, что вы делаете, разница не актуальна, подумайте, что произойдет, если вы захотите создать дерево DFS (чтобы вы сохранили все используемые ребра). Рассмотрим следующий (ненаправленный) график:

A -- B -- C -- D
     |---------|     <- connection between B and D

Теперь мы запускаем DFS на узле A. Произойдет следующее:

head | st     | used edge | saved edges
A    | B      |           |
B    | C, D   | A -- B    | A -- B
C    | D      | B -- C    | A -- B, B -- C
D    |        | B -- D    | A -- B, B -- C, B -- D

Соответствующая часть, которую вы используете B -- D , поскольку вы отмечаете D в первый раз, когда вы сталкиваетесь с этим. Таким образом, ваше дерево DFS будет выглядеть так:

A -- B -- C
     |
     D

, что неправильно. Это должно выглядеть так:

A -- B -- C -- D          // C and D can be exchanged

Это актуально? Для определенных приложений DFS это так. Для простого нахождения узла каким-либо способом это не имеет значения, вы все равно будете проверять весь график таким образом. Действительно, DFS в основном используется как простой алгоритм сбора графов, поэтому для ребер используется, вероятно, неважно почти для всех приложений. (На самом деле я могу сейчас думать только о том, где это важно)