带堆栈的 DFS 在有向、非循环、未加权的图中查找从某个节点开始的最长路径的长度

Question

我正在尝试找出一种方法来实现 DFS 搜索，以通过使用堆栈而不使用递归来查找表示为邻接列表的有向图上给定节点的最长路径的长度。具体来说，我想实现 DFS 搜索，以便在它运行时填充堆栈，如下图所示..

如果不清楚，这个视频是我希望在我的程序运行时构建堆栈的方式（DFS 在 12:45 左右开始：https://www.youtube.com/watch?v=pcKY4hjDrxk 但是我正在努力寻找一种方法来实现这一目标，因为我对一般的编程仍然很陌生。我当前的代码将图形表示为无序映射，每个条目都包含指向它的所有节点的向量。即：

std::unordered_map<long, std::vector<long>> nodes;

基本上，我想从所有节点实现 DFS 搜索，其中 unordered_map 中的键值为 -1，如图和视频中所示 - 堆栈如图所示分配。我在想，这样我就可以在堆栈达到最大时记录下来，那将是最长的路径。

需要注意的是，在这个具体问题的图形中，每条边只有一个出度，如图所示。。这是可能的，还是我必须使用某种递归来做我想做的事？在此先感谢您的帮助。

Answer 1

您或许可以使用任务列表而不是递归。如果像队列一样以 FIFO 顺序使用任务列表，就会得到广度优先搜索；如果你像堆栈一样使用它，后进先出，你会得到深度优先的行为。

但是请注意，具有 N 个节点的 DAG 可能有 O(2^(N/2)) 个可能的路径！但是，您不需要评估所有可能的路径来解决您的问题，因此请注意不要编写可能需要指数时间的算法。

为此，您需要标记已处理的节点。此外，由于您正在寻找最长路径，因此您需要跟踪每个节点的有关迄今为止找到的最长路径的信息。

Answer 2

尽管无需递归也可以实现这一点，但作为替代方案，我建议您以这种方式设计一个函数，这需要您编写更少的代码，并且会提供很好的直觉来帮助您理解该算法'是初学者。而且你不需要考虑自己创建堆栈

const int n = 100;
vector< int > graph[n];
int ans = 0, level = 0;
int vis[n];
void dfs(int src) {
  level++;
  ans = max(level, ans);
  for (int x: graph[src]) {
    if(vis[x]) continue;
    vis[x] = 1;
    dfs(x);
    level--;
  }
}

我对 n 和图形的值进行了硬编码，您可以根据需要根据需要更改它的结构。

我们利用程序为递归树创建的堆栈的优势。对于给定的 V 节点和 E 边图，此函数将在 O(V+E) 中工作。

注意，如果你的Graph很大，程序默认创建的栈无法处理，那你还是要自己写栈来处理递归。

带堆栈的 DFS 在有向、非循环、未加权的图中查找从某个节点开始的最长路径的长度

DFS with stack to find length of longest path from a certain node in a directed, acyclic, unweighted graph

c++

algorithm

tree

graph

depth-first-search