連接的設備計數算法

Question

我一直在尋找到連接組件的運行時間，和整個本說明書來到Wikipedia：

這是簡單的計算線性時間的圖 的連接部件（在使用廣度優先搜索或深度優先搜索來確定圖的頂點和邊的數量項）。在任何一種情況下，從某個特定頂點v開始的搜索 將在返回 之前找到包含v（且不再有）的整個連接組件。要查找圖形的所有連接組件，請通過其頂點循環 ，首先開始新寬度或深度優先 搜索循環何時到達尚未包含在以前找到的連接組件中的 的頂點。

該操作的運行時間是多少？我發現有消息稱，連接的組件在O(n)時間內完成。但是，從我所知道的情況來看，在最壞的情況下，每個頂點都是自己的連接組件，該算法將不得不執行n個DFS/BFS操作，每個操作本身都是O(n)時間。所以，不應該這樣做的運行時間是O(n^2)？

Answer 1

首先，使用DFS或BFS |V|頂點和邊緣|E|單個連接成分G(V, E)的橫移具有O(|V|+|E|)複雜性。

線性時間（在頂點和 圖的邊的數量而言）

讓我們假設圖G(V, E)具有k連接的組件。

G(V, E) = G1(V1, E1) ∪ G2(V2, E2) ∪ ... ∪ Gk(Vk, Ek) 

每個部件Gi可以與DFS/BFS在O(|Vi|+|Ei|)找到。其結果是，對於每一個未訪問的頂點開始DFS或BFS遍歷其連通分量算法的總時間是：

O(|V1|+|E1|) + O(|V2|+|E2|) + ... + O(|Vk|+|Ek|) + O(|V|) 

這些組件沒有任何共同的頂點或邊，因爲它們不連接。所以：

|V| = |V1| + |V2| + ... + |Vk| 
|E| = |E1| + |E2| + ... + |Ek| 

最後，連成分計算的整體複雜性是：

O(|V1|+|E1|) + O(|V2|+|E2|) + ... + O(|Vk|+|Ek|) + O(|V|) = 
O(|V1|+|V2|+...+|Vk| + |E1|+|E2|+...+|Ek|) + O(|V|) = 
O(|V|+|E|) + O(|V|) = 
O(|V|+|E|)