如何更有效地递归搜索最长节点？

Question

我试图在有向无环图中找到最长的路径。目前，我的代码似乎是运行 O(n³).

的时间复杂度

图表是输入{0: [1,2], 1: [2,3], 3: [4,5] }

#Input: dictionary: graph, int: start, list: path
#Output: List: the longest path in the graph (Recurrance)
# This is a modification of a depth first search
def find_longest_path(graph, start, path=[]):
    path = path + [start]
    paths = path
    for node in graph[start]:
        if node not in path:
            newpaths = find_longest_path(graph, node, path)
            #Only take the new path if its length is greater than the current path
            if(len(newpaths) > len(paths)):
                paths = newpaths

    return paths

它 returns 表单中的节点列表，例如[0,1,3,5]

如何使它比 O(n³) 更有效？递归是解决这个问题的正确方法还是我应该使用不同的循环？

Answer 1

你可以在 O(n+e) 内解决这个问题（即与节点数 + 边数呈线性关系）。

这个想法是你首先创建一个拓扑排序（我是 Tarjan's algorithm 的粉丝）和一组反向边缘。如果您可以分解问题以利用现有解决方案，它总是有帮助的。

然后，您将拓扑排序向后推到每个父节点，其子节点的距离 + 1（在存在多条路径的情况下保持最大值）。跟踪到目前为止看到的距离最大的节点。

当你用距离完成对所有节点的注释后，你可以从距离最大的节点开始，这将是你最长的路径根，然后沿着你的图表走下去，选择正好少一个的子节点比当前节点（因为它们位于关键路径上）。

一般来说，在尝试寻找最佳复杂度算法时，不要害怕一个接一个地运行多个阶段。五 O(n) 算法运行顺序仍然是 O(n) 并且仍然优于 O( n²) 从复杂性的角度来看（尽管根据常量 costs/factors 和 n).

ETA: 我刚注意到你有一个起始节点。这使得它只是一个进行深度优先搜索并保持迄今为止看到的最长解决方案的情况，无论如何只是 O(n+e) 。递归很好，或者您可以保留 list/stack 个已访问节点（每次回溯时查找下一个子节点时必须小心）。

当您从深度优先搜索回溯时，您需要存储从该节点到叶子的最长路径，这样您就不会重新处理任何子树。这也将作为一个 visited 标志（即除了进行 node not in path 测试之外，在递归之前还有一个 node not in subpath_cache 测试）。您可以存储长度，而不是存储子路径，然后根据上面讨论的顺序值（关键路径）完成后重建路径。

ETA2:这是一个解决方案。

def find_longest_path_rec(graph, parent, cache):
    maxlen = 0
    for node in graph[parent]:
        if node in cache:
            pass
        elif node not in graph:
            cache[node] = 1
        else:
            cache[node] = find_longest_path_rec(graph, node, cache)

        maxlen = max(maxlen, cache[node])

    return maxlen + 1

def find_longest_path(graph, start):
    cache = {}
    maxlen = find_longest_path_rec(graph, start, cache)
    path = [start]
    for i in range(maxlen-1, 0, -1):
        for node in graph[path[-1]]:
            if cache[node] == i:
                path.append(node)
                break
        else:
            assert(0)
    return path

请注意，我已经删除了 node not in path 测试，因为我假设您实际上是在提供所声称的 DAG。如果你想要检查你真的应该提出错误而不是忽略它。另请注意，我已将断言添加到 for 的 else 子句中，以记录我们必须始终在路径中找到有效的下一个（顺序）节点。

ETA3: 最后的 for 循环有点混乱。我们正在做的是考虑在关键路径中所有节点距离必须是连续的。考虑节点 0 的距离为 4，节点 1 的距离为 3，节点 2 的距离为 1。如果我们的路径开始 [0, 2, ...]，我们就会产生矛盾，因为节点 0 与叶子的距离并不比 2 更远。

Answer 2

我建议进行一些非算法改进（这些与 Python 代码质量有关）：

def find_longest_path_from(graph, start, path=None):
    """
    Returns the longest path in the graph from a given start node
    """
    if path is None:
        path = []
    path = path + [start]
    max_path = path
    nodes = graph.get(start, [])
    for node in nodes:
        if node not in path:
            candidate_path = find_longest_path_from(graph, node, path)
            if len(candidate_path) > len(max_path):
                max_path = candidate_path
    return max_path

def find_longest_path(graph):
    """
    Returns the longest path in a graph
    """
    max_path = []
    for node in graph:
        candidate_path = find_longest_path_from(graph, node)
        if len(candidate_path) > len(max_path):
            max_path = candidate_path
    return max_path

更改说明：

def find_longest_path_from(graph, start, path=None):
    if path is None:
        path = []

我已将 find_longest_path 重命名为 find_longest_path_from 以更好地解释它的作用。
将 path 参数更改为具有默认参数值 None 而不是 []。除非你知道你将特别受益于它们，否则你希望避免使用可变对象作为 Python 中的默认参数。这意味着您通常应该默认将 path 设置为 None，然后在调用该函数时，检查是否 path is None 并相应地创建一个空列表。

max_path = path
...
candidate_path = find_longest_path_from(graph, node, path)
...

我已将您的变量名称从 paths 更新为 max_path，将 newpaths 更新为 candidate_path。这些变量名令人困惑，因为它们指的是路径的复数形式——暗示它们存储的值由多条路径组成——而实际上它们每个都只有一条路径。我试着给他们起更具描述性的名字。

nodes = graph.get(start, [])
for node in nodes:

您的代码在示例输入中出错，因为图的叶节点不是 dict 中的键，因此 graph[start] 会在 start 时引发 KeyError例如 2。这通过返回一个空列表来处理 start 不是 graph 中的键的情况。

def find_longest_path(graph):
    """
    Returns the longest path in a graph
    """
    max_path = []
    for node in graph:
        candidate_path = find_longest_path_from(graph, node)
        if len(candidate_path) > len(max_path):
            max_path = candidate_path
    return max_path

一种在遍历键的图中查找最长路径的方法。这与您对 find_longest_path_from 的算法分析完全不同，但我想将其包括在内。

如何更有效地递归搜索最长节点？

How can I make a recursive search for longest node more efficient?

python

graph-algorithm