你如何計算連接圖的數量？

Question

給定一個節點數組和邊數組，你如何計算連接圖的數量？

Answer 1

• 從其中一個節點開始執行BFS或DFS以獲取從此節點連接的所有節點。
• 現在遍歷節點列表以找到任何未包含的節點，
• 在節點上執行相同的過程。重複直到所有節點都被訪問。
• 現在您將擁有數據中的所有圖表。

Answer 2

是，有一種算法是在圖中的尺寸，O-線性（| V | + | E |）。

visited := the empty set 
count := 0 
for each vertex v in vertices: 
    if v not in visited: 
     count++ 
     add v and all nodes reachable from v to visited 
return count 

Answer 3

您可以使用聯合查找（您可以搜索它）。從所有節點開始，作爲單獨的集合，然後爲每個邊緣連接邊緣連接到同一集合的兩個節點。然後通過遍歷所有節點並查找有多少個不同的代表，檢查有多少個不同的集合。

Answer 4

爲了詳細說明quasiverse的回答，下面是一個簡短的僞代碼：

MAKE_SET（V）創建一個新的組，其唯一的成員爲v

聯盟（X，Y）聯合了兩套。 x和y。新組的代表元素從兩組中選擇一個

get_representatve（v）返回給定節點所屬組的代表。

查找圖G =（V，E）連接的部件：

foreach vertex v in V: 
    make_set(v) 

foreach edge (u, v) in E: 
    if get_representatve(u) != get_representatve: 
     union(u, v) 

實現必要的功能是爲讀者;-)反正它會工作的優良無向圖的鍛鍊，但是如果你需要強大的連接組件，你應該看看Tarjan的算法。

對於並行實現，存在一個沒有工作效率的確定性算法，但存在一些有趣的隨機算法。

Answer 5

對於無向圖，這可以在O（n）時間內用簡單的DFS完成。方法如下：

將explore定義爲查找可以從給定節點到達的所有節點的過程。這只是一個類似DFS的遞歸過程，在每個節點上，您可以找到該節點的所有子節點並將它們推送到堆棧中。

要找到答案，請在任何節點上啓動DFS，並在該節點上啓動explore過程。每次調用時，保留一個整數（例如cc）並將其傳遞給explore過程。另外，保留一個hashmap/dictionary或者將cc映射到相應的節點。在explore過程的每個級別，此時將當前節點映射到cc。每次探索過程被遞歸地調用時，將其傳遞給相同的值cc。

每當explore返回到DFS循環時，都會增加cc並在下一次傳遞該值。一旦完成了整個DFS，就會有一個字典將每個節點映射到相應的連接組件編號。此過程結束時的值cc可以爲您提供圖中連接組件的數量。

這裏是僞代碼：

function explore(node, graph, cc, map){ 
    map(currentNode) = cc 
    //find all children of current node, and push onto stack. 
    //mark current node as visited 
    for i in stack: 
     explore(i, graph, cc, map) 
} 

function DFS{ 
    int cc = -1 
    for node in keysOfGraph: 
      if not visited: 
       cc++ 
       explore(node, graph, cc, map) 

return cc 
} 

從Dasgupta Algorithms（3.2.3節）