图表中最长的路径

问题描述 投票:1回答:3

给定一个顶点形式为0到n-1的无向图,写一个函数,找到最长的路径(按边数),哪个顶点构成一个递增的序列。

你会推荐什么样的方法来解决这个难题?

graph-algorithm
3个回答
5
投票

您可以将原始图形转换为有向非循环图形,方法是将每个(无向)边缘替换为朝向具有较大数字的节点的有向边缘。

然后你最终得到这个:https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/


1
投票

我会做一个动态编程算法。将L(u)表示为从节点u开始的最长有效路径。您的基本情况是L(n-1)= [n-1](即,仅包含节点n-1的路径)。然后,对于从n-2到0的所有节点,执行从s开始的BFS,其中您只允许遍历边(u,v),使得v> u。一旦你点击了你已经开始的节点(即你已经计算过L(u)的节点u),L(s)=从s到u + L(u)的最长路径所有可能的u> s。

问题的答案是节点u的最大值为L(u),此算法为O(E),其中E是图中边的数量。我不认为你可以比渐近地做得更快

编辑:实际上,“BFS”甚至不是BFS:它只是遍历边缘(s,v),使得v> s(因为你已经访问过所有节点v> s,所以没有遍历:你会立即点击你已经开始的节点)

实际上,简化的算法是这样的:

longest_path_increasing_nodes():
    L = Hash Map whose keys are nodes and values are paths (list of nodes)
    L[n-1] = [n-1] # base case
    longest_path = L[n-1]
    for s from n-2 to 0: # recursive case
        L[s] = [s]
        for each edge (s,v):
            if v > s and length([s] + L[v]) > length(L[s]):
                L[s] = [s] + L[v]
        if L[s] > longest_path:
            longest_path = L[s]
    return longest_path

-1
投票

有像Dijkstra算法这样的算法可以修改以找到最长而不是最短的路径。

这是一个简单的方法:

  • 使用递归算法查找2个节点之间的所有路径。
  • 选择最长的路径。

如果您需要有关递归算法的帮助,请询问。

© www.soinside.com 2019 - 2024. All rights reserved.