在未加权图中找到最长路径

Question

我在这个问题上遇到了很大的困难。

如果我有一个图，有向或无向，未加权且没有循环。如何找到最长的路径？ 我见过的许多算法都依赖于对图进行加权，并反转权重并使用贝尔曼福特。 我也见过动态规划解决方案，但这里的人们只是在寻找任何路径，我正在寻找来自 s-t 的路径。

我一直在尝试将图分解为子问题，其中我一次添加一个节点，并给它一个来自父节点的值加一，但我只是无法获得正确的逻辑

谁能提供一种算法，指数时间就可以，伪多项式就很棒了？

Answer 1

如果图可以是有向的 或无向的，那么我们可以将问题简化为仅针对有向图。如果它是无向的，那么您应该从 v -> w 和 w -> v 建立边。您可以使用修改后的 DFS 来测量从传递给此函数的节点开始的最长路径。 然后对每个节点运行这个函数并获取最大值。

DFS 的伪代码：

DFS(Node v):
  if (v.visited?) return 0;
  v.visited = true;
  longestPath = 0;
  foreach(Node n : v.neighbours):
    longestPath = max(longestPath, DFS(n) + 1)
  return longestPath

问题的伪代码：

longestPath(Node[] verticies):
  longestPath = 0
  foreach(Node v : vertices):
    foreach(Node w: vertices):
      w.visited = false;
    longestPath = max(longestPath, DFS(v))
  return longestPath;

它的工作时间为 O(n^2)，但我认为这个解决方案很简单。 只是想让你知道，有一个解决方案的工作时间复杂度为 O(n)。

Answer 2

您可以使用改进的 DFS 通过执行两次 DFS 来找到它 O(n)。首先，您从随机节点执行 dfs，找到距该节点最远的节点，然后再次从找到的节点执行 dfs。我解决了一个 leetcode 问题，需要这个，所以如果你想查看代码，这里是链接。 https://leetcode.com/problems/minimum-height-trees/solutions/5061978/c-twice-dfs-solution/