求解图连通分量两种算法的时间复杂度

第一种算法的时间复杂度 #

先看算法代码：

for each node in the graph:
    set its component to its value;   // O(V)
for every edge in the graph:
    if its end vertices are in different components  
       set all the nodes in each of their components to the same component        // 最坏O(V)

• 初始化阶段：遍历所有顶点完成赋值，时间复杂度为O(V)。
• 核心边处理阶段：循环执行E次（E为边数），但每次合并操作的最坏时间是O(V)。举个极端例子：图为一条线性链（V个顶点，V-1条边），每次处理边时，两个分量的大小分别为1和V-1，合并时需要遍历所有V个顶点修改分量标记。这种情况下，总操作次数是EV≈V²，因此整体时间复杂度为**O(VE)**。
  你之前的O(V+E)猜想不成立，因为合并操作不是常数时间，最坏情况下每次合并都要遍历大量顶点，导致整体复杂度是顶点数和边数的乘积。

第二种邻接表DFS算法的时间复杂度验证 #

算法代码如下：

components(G):
  for all vertices v ∈ G:
    componentOf[v] = -1
  compID = 0  // component ID
  for all vertices v ∈ G:
    if componentOf[v] == -1:
      dfsComponent(G, v, compID)
      compID = compID + 1
 
dfsComponent(G, v, id):
  componentOf[v] = id
  for each (v,w) ∈ edges(G):
    if componentOf[w] == -1:
      dfsComponent(G, w, id)

你的O(EV + V²)猜想错误，实际时间复杂度为O(V + E)，推导如下：

• 初始化阶段：遍历所有顶点设置标记，时间O(V)。
• DFS遍历阶段：每个顶点只会被访问一次（标记componentOf后不会再进入递归）；每条边在邻接表中会被遍历一次（无向图中每条边存两次，但每个方向仅在对应顶点被访问时处理一次，且不会重复处理）。所有顶点和边的处理次数都是常数级，因此总时间是顶点数加边数的线性复杂度。

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