时间戳

首页 > 解决方案 > 迭代 DFS——在哪里将节点标记为已访问？

c++ - 迭代 DFS——在哪里将节点标记为已访问？

问题描述

这是我根据我在这里看到的一些建议对迭代 dfs 的实现，这些建议声明将节点添加到堆栈后立即将其标记为已访问。

我查看了其他一些实现，例如https://www.geeksforgeeks.org/iterative-depth-first-traversal/，其中一个节点在从堆栈中删除后被标记为已访问。我见过的大多数实现在将其从堆栈中删除后将其标记为已访问。以这种方式实施它与我所做的相比有什么优势？在这个版本中，即使您已经访问过当前节点，看起来您仍然会执行 for 循环。在我的版本中，您永远不会遇到为访问的节点执行 for 循环的情况。

进一步查看我当前的代码后，我发现我在将其放入堆栈之前将其标记为已访问。正确的方法是在将其放入堆栈后将其标记为已访问吗？

#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);
}

标签： c++depth-first-search

解决方案

您的代码实际上并不执行 DFS。对于您所做的，差异无关紧要，想想会发生什么，如果您想创建一个 DFS 树（这样您就可以保存所有使用的边）。考虑以下（无向）图：

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

现在我们在节点 A 启动 DFS。会发生以下情况：

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 主要用作简单的图集合算法，因此边缘对于几乎所有应用程序来说可能并不重要。（其实我现在只能想到一个重要的地方）

推荐阅读