从输入节点开始查找最大长度n的所有路径的时间复杂度

Question

我写了一个简单的算法，它是 DFS 的变体。

这个想法是在有向图中找到从给定输入节点 u 开始的最大长度 n 的所有路径。

下面是python代码：

def find_paths(G, u, n, n_recursive):
    paths = []
    if n_recursive == 0:
        return [[u]]
    if n_recursive < n:
        paths.append([u])
    for neighbor in G.neighbors(u):
        for path in find_paths(G, neighbor, n, n_recursive - 1):
            if u not in path:
                paths.append([u] + path)
    return paths

输出只是一个列表列表。在每个内部列表中，都有该路径经过的节点的有序列表。 下面是一个图表示例和算法的输出。

find_paths(G=g, u=0, n=3, n_recursive=3)

的输出（来自节点0的最大长度3的所有路径）：

[[0, 1],
[0, 1, 2],
[0, 1, 2, 3],
[0, 1, 2, 5],
[0, 1, 2, 6],
[0, 2],
[0, 2, 3],
[0, 2, 3, 4],
[0, 2, 5],
[0, 2, 6]]

我知道DFS的复杂度是O(|V|+|E|)（在邻接表的情况下）。如何计算这个算法的复杂度？老实说我不知道从哪里开始

谢谢大家。

Answer 1

我知道 DFS 的复杂度是 O(|V|+|E|)（在邻接表的情况下）。

当您想要访问图表的所有节点时，确实如此。在这种情况下，递归函数可能会从顶层多次调用，因为图形可能具有断开连接的组件。

但是您的用例是不同的，因为您只对从给定节点开始的路径感兴趣，因此您不会有来自顶层的多个调用。这意味着 |V|不会对复杂性产生影响。另一方面，您允许多次访问边缘，因为它们是通过不同的路径访问的。这意味着输出大小的复杂度不是 O(|E|)。

在进一步分析之前，首先进行优化，因为这个语句有一个瓶颈：

paths.append([u] + path)

这不是 O(1) 复杂度，而是 O(路径长度)。这是可以避免的。相反，将

u

附加到 path 的

end

处（对其进行变异），然后将该路径附加到

paths

。这意味着您的结果将具有相反顺序的所有路径，但您可以更改此顺序作为一种后处理。所以上面的代码应该改为：

path.append(u)
paths.append(path)

通过此更改，算法的时间复杂度由这些

append

调用发生的次数决定，换句话说，它等于输出的大小。

输出的大小不是 O(|E|)。以这张图为例：

它有 19 个节点和 24 条边，但我们可以想象它会这样继续下去，这样我们就有 3𝑘+1 个节点和 4𝑘 边。现在假设我们想要从最左边的节点开始所有长度为 2𝑘 的路径，那么我们可以在每个“交叉点”（和起始节点）在 2 个选项之间做出选择，所以总共有 2 _𝑘 路径，每个路径有 𝑘 + 1 个节点。所以输出大小是 O(𝑘2_𝑘)，并且由于 𝑘 在这个特定类别的图中是 O(|E|)，因此输出大小在这里是 O(|E|2^|E|)，这也是是时间复杂度。

这种指数复杂性的原因不是你的算法本身，而是你想要实现的具体目标。