带堆栈的DFS，用于在有向、无环、无加权图中从某个节点找到最长路径的长度

Question

我试图找到一种实现DFS搜索的方法，通过使用堆栈，而不是使用递归，在表示为邻接列表的有向图上找到从给定节点开始的最长路径的长度。具体地说，我希望实现DFS搜索，以便在运行时，如下图所示填充堆栈。。

如果这还不清楚的话，这段视频是我希望在html" target="_blank">程序运行时如何构建堆栈的（DFS大约在12:45开始：https://www.youtube.com/watch?v=pcKY4hjDrxk 但我正在努力找到一种方法来实现这一点，因为我对编程总体来说还是相当陌生。我当前的代码将图形表示为无序映射，每个条目包含指向它的所有节点的向量。例如：

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

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

Answer 1

虽然没有递归也可以实现这一点，但作为一种选择，我建议你这样设计一个函数，这需要你写更少的代码，这将为初学者提供理解这个算法的良好直觉。你不需要考虑自己创建堆栈

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（ve）中工作。

请注意，如果图形太大，以至于程序默认创建的堆栈无法处理，那么您仍然需要编写自己的堆栈来处理递归。

Answer 2

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

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

为此，需要标记已处理的节点。此外，由于要查找最长路径，因此需要跟踪每个节点到目前为止找到的最长路径的相关信息。