求无向图中长度为n的环计数算法的时间复杂度

问题描述 #

我目前正在学习编程，难以理解网上找到的以下算法的时间复杂度，希望能得到帮助。我知道普通DFS的时间复杂度为O(V+E)，但该算法在检查是否形成环前仅为每个节点检查3条路径。

算法代码 #

# Python Program to count cycles of length n in a given graph. 

# Number of vertices 
V = 5

def DFS(graph, marked, n, vert, start, count): 

    # mark the vertex vert as visited 
    marked[vert] = True

    # if the path of length (n-1) is found 
    if n == 0: 

        # mark vert as un-visited to make 
        # it usable again. 
        marked[vert] = False

        # Check if vertex vert can end with 
        # vertex start 
        if graph[vert][start] == 1: 
            count = count + 1
            return count 
        else: 
            return count 

    # For searching every possible path of 
    # length (n-1) 
    for i in range(V): 
        if marked[i] == False and graph[vert][i] == 1: 

            # DFS for searching path by decreasing 
            # length by 1 
            count = DFS(graph, marked, n-1, i, start, count) 

    # marking vert as unvisited to make it 
    # usable again. 
    marked[vert] = False
    return count 

# Counts cycles of length N in an undirected and connected graph. 
def countCycles( graph, n): 

    # all vertex are marked un-visited initially. 
    marked = [False] * V 

    # Searching for cycle by using v-n+1 vertices 
    count = 0
    for i in range(V-(n-1)): 
        count = DFS(graph, marked, n-1, i, i, count) 

        # ith vertex is marked as visited and 
        # will not be visited again. 
        marked[i] = True

    return int(count/2) 

# main : 
graph = [[0, 1, 0, 1, 0], 
        [1 ,0 ,1 ,0, 1], 
        [0, 1, 0, 1, 0], 
        [1, 0, 1, 0, 1], 
        [0, 1, 0, 1, 0]] 

n = 4
print("Total cycles of length ",n," are ",countCycles(graph, n))

时间复杂度分析 #

这个算法和普通DFS的定位完全不同，普通DFS是遍历图的所有节点和边，而这个算法的核心是枚举所有长度为n的简单环，所以复杂度不能用普通DFS的O(V+E)来套用，具体拆解如下：

1. 外层循环的复杂度
   countCycles函数中的循环执行V - n + 1次，这个量级属于O(V)——因为n是固定的目标环长度，相对于顶点数V来说是常数项。

2. 单次DFS的复杂度
   每次DFS的目标是找到从起始节点出发、长度为n-1的所有简单路径（路径中无重复节点，由marked数组保证）：

• 递归深度固定为n-1层，每一层递归时，当前节点会遍历所有未被标记的邻接节点。
• 假设每个节点的平均邻接数（度）为D（你提到的“每个节点检查3条路径”对应D=3），那么每一层最多有D个分支选择，递归n-1层后，总的操作数就是O(D^(n-1))。

3. 整体时间复杂度
   将外层循环和单次DFS的复杂度相乘，整体时间复杂度为O(V * D^(n-1))。当n较大时，这是一个指数级复杂度的算法，因为D的n-1次方会随n快速增长。

为什么和普通DFS不同？ #

普通DFS的目标是遍历整个图，每个节点和边只会被访问一次，所以是线性复杂度O(V+E)。而这个算法是在枚举所有符合长度要求的路径，每一步都要探索所有可能的分支，本质是穷举，所以复杂度随目标环长度n呈指数增长，这是这类枚举型算法的固有特性。

内容的提问来源于stack exchange，提问作者JSM77