深度优先搜索(DFS)时间复杂度疑问：为何实际结果与O(V+E)不符？

我写了一段实现无向图深度优先搜索(DFS)的Python代码：

def add_edge(adj, s, t):
    # Add edge from vertex s to t
    adj[s].append(t)
    # Due to undirected Graph
    adj[t].append(s)
    print('adj add edge', adj)


def dfs_rec(adj, visited, s, loop_count):
    # Mark the current vertex as visited
    visited[s] = True
    print(f'Visited vertex: {s}')

    # Recursively visit all adjacent vertices
    for i in adj[s]:
        loop_count[0] += 1  # Increment the loop counter
        if not visited[i]:
            dfs_rec(adj, visited, i, loop_count)


def dfs(adj, s):
    visited = [False] * len(adj)
    print('Initial visited list:', visited)

    # Create a list to hold loop count as a mutable object
    loop_count = [0]  # This will hold the number of times the loop runs

    # Start DFS recursion
    dfs_rec(adj, visited, s, loop_count)

    # Return the loop count
    return loop_count[0]


if __name__ == "__main__":
    V = 5

    # Create an adjacency list for the graph
    adj = [[] for _ in range(V)]

    # Define the edges of the graph
    edges = [[1, 2], [1, 0], [2, 0], [2, 3], [2, 4], [1, 3], [1, 4], [3, 4], [0, 3], [0, 4]]

    # Populate the adjacency list with edges
    for e in edges:
        print('Adding edge:', e)
        add_edge(adj, e[0], e[1])

    source = 1
    print(f"\nDFS traversal from source vertex: {source}")
    total_loops = dfs(adj, source)
    print(f"Total number of times the for loop ran: {total_loops}")

运行后得到输出：

Total number of times the for loop ran: 20

已知DFS的时间复杂度应为O(V+E)，但我误以为边数E为5，此次运行结果看起来符合O(E²)的特征，这让我困惑：为何实际运行结果与理论复杂度不符？我的理解误区在哪里？

解答 #

1. 边数E的计算完全错误 #

你定义的edges列表包含10条边，这是5个顶点的完全图（任意两个顶点之间都有一条边）。无向完全图的边数公式为C(n,2) = n*(n-1)/2，代入n=5得到10条边，和你以为的5条完全不符。

2. 循环计数统计的是邻接表总元素数，而非无向边数E #

无向图的邻接表中，每条边会被存储两次（比如边1-2会同时出现在顶点1和顶点2的邻接列表里），因此邻接表的总元素数量是2E。你的loop_count统计的是所有递归调用中遍历邻接表元素的总次数，也就是2E。对于E=10的情况，2×10=20，正好和运行结果匹配。

3. 对时间复杂度的量级理解偏差 #

DFS的时间复杂度O(V+E)中的E指的是无向边的数量，邻接表遍历的总次数是O(V + 2E)，但复杂度分析中会忽略常数系数，因此依然属于O(V+E)的线性量级。你的结果20是线性增长的结果，和O(E²)的平方级增长完全无关——如果是O(E²)，E=10时结果会是100左右，显然和你的输出不符。

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