邻接表存储无向图traversal算法最坏时间复杂度求解

设$G=(V, E)$为一个拥有$n$个顶点且$m>n$条边的无向连通图，所有顶点初始未标记且存储在数组$V$中，考虑以下算法：

Algorithm traversal(G)
Input: Undirected, connected graph G.
c←0
for i ← 0 to n − 1 do {
     u ← V [i]
     for each edge (u, v) incident on u do {
           Mark u
           if v is not marked then c ← c + 1 }
}

假设$G$以邻接表存储，算法traverse(G)最坏情况下的时间复杂度是什么？选项如下：

• (A) O(n)
• (B) O(n²)
• (C) O(n × degree(u))
• (D) O(m)
• (E) O(nm)

正确答案：(D) O(m) #

推导过程： #

1. 邻接表遍历特性：无向图的邻接表中，每条边会被存储两次（分别在两个端点的邻接链表中），遍历所有顶点的邻接边的总次数为$2m$，属于$O(m)$量级。
2. 算法执行逻辑：外层循环遍历$n$个顶点，但每个顶点的内层循环仅遍历自身的邻接边（次数等于该顶点的度数$\text{degree}(u)$）。根据无向图的握手定理，所有顶点的度数之和$\sum_{u \in V} \text{degree}(u) = 2m$，因此总遍历操作次数与$m$线性相关。
3. 错误选项排除：
   • (A) 显然不成立，$m>n$时遍历边的次数远多于顶点数。
   • (B) 仅在完全图（$m=\frac{n(n-1)}{2}$）这类特殊场景下等价于$O(n^2)$，但这只是$O(m)$的特例，并非通用最坏情况复杂度。
   • (C) $\text{degree}(u)$是单个顶点的度数，该表达式无法代表总遍历次数，总次数是所有顶点度数之和而非$n$乘以某个顶点的度数。
   • (E) $O(nm)$错误，邻接表中每个顶点仅遍历自身邻接边，不会重复遍历所有$m$条边$n$次，总操作次数仅为$O(m)$级别。

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