c++ - 计算图中路径的递归函数的复杂性

Question

我找到了一个用于有向图的函数，对于其中的顶点“u”和“v”，它会计算从“u”到“v”的所有可能路径，其中正好有 k 个边。 代码和算法来自here .所以，

// C++ program to count walks from u to v with exactly k edges
#include <iostream>
using namespace std;

// Number of vertices in the graph
#define V 4

// A naive recursive function to count walks from u to v with k edges
int countwalks(int graph[][V], int u, int v, int k)
{
   // Base cases
   if (k == 0 && u == v)      return 1;
   if (k == 1 && graph[u][v]) return 1;
   if (k <= 0)                return 0;

   // Initialize result
   int count = 0;

   // Go to all adjacents of u and recur
   for (int i = 0; i < V; i++)
       if (graph[u][i])  // Check if is adjacent of u
           count += countwalks(graph, i, v, k-1);

   return count;
}

我试图找到并证明这个算法的复杂性。根据帖子:

"The worst case time complexity of the above function is O(V^k) where V is the number of vertices in the given graph. We can simply analyze the time complexity by drawing recursion tree. The worst occurs for a complete graph. In worst case, every internal node of recursion tree would have exactly n children."

但是，我找不到导致我可以分析以证明此算法为 O(V^k) 的树的递归。另外，我认为最好的情况是 Theta(1)。真的吗？平均情况如何？

Answer 1

对于一个完整的图，每个节点都与其他节点相连，因此您的 for 循环将进行 |V| 递归调用。这将在每次递归调用时发生，直到 k 变为 1，因此总共 O(|V|^k) 次递归调用。

可以这样表达:

T(V, k) = |V|*T(V, k - 1)
        = |V|*|V|*T(V, k - 2)
        = |V|^2*|V|*T(V, k - 3)
        = ...

总是T(V, _) 因为一个节点可以被多次访问。

当在第一次调用期间触发前三个 if 条件之一时，最好的情况确实是 O(1)。

平均情况我不确定，但我认为它应该仍然很糟糕。考虑一个链表图和一个巨大的 k:为了使 k 变为 0 或 1，您将多次遍历相同的边。随着添加的越多，情况会变得越来越糟路径。