在圖中查找連接的組件

如果我有一個無向圖（作爲頂點列表實現），我如何找到它的連接組件？我如何使用快速聯合？在圖中查找連接的組件

2014-01-12 abalcerek

頂點表示爲列表，但邊如何表示？ –

圖G是一列整數列表。如果f在列表G [i]上並且我在G [j]上，則存在邊緣形式i到j。 – abalcerek

這個問題似乎是脫離主題，因爲它是關於計算機科學，而不是編程，屬於http://cs.stackexchange.com/ –

使用深度優先搜索（DFS）來標記所有的單個連接的組件爲已訪問：

dfs(node u) 
    for each node v connected to u : 
    if v is not visited : 
     visited[v] = true 
     dfs(v) 


for each node u: 
    if u is not visited : 
    visited[u] = true 
    connected_component += 1 
    dfs(u)

的最佳方式是使用本直接的方法是線性時間爲O（n）。
既然你問到的合併 - 查找算法：

for each node parent[node] = node 

for each node u : 
    for each node v connected to u : 
     if findset(u)!=findset(v) : 
      union(u,v) 

**I assume you know about how findset and union works ** 
for each node if (parent[node] == node) 
    connected_component += 1

來源

2014-01-12 18:43:19

是否有任何理由使用dfs over bfs？ – Will

@是的，因爲BFS首先從你選擇的節點「X」開始覆蓋「圖層」中的圖形，這意味着如果某個節點'Y'不能從'X'到達，那麼BFS將不會訪問它。雖然DFS在這種情況下會這樣做，爲什麼呢？因爲當你從'X'覆蓋所有可到達的節點並且還有一些未訪問節點時，則DFS將從其中一個節點重新開始，因此DFS爲您提供了一個森林，而BFS則爲您提供了一棵樹。 – ThunderWiring

@ThunderWiring我不知道我明白。什麼阻止我們從這些未訪問/未發現的節點之一運行BFS？在DFS的定義中似乎沒有必要爲圖中每個未發現的節點運行它。如果您在每個未發現的節點上運行BFS或DFS，您將獲得連接組件的森林。 –

對於每一個edge(u,v)找到union(u,v)使用快速合併 - 查找數據結構並找到設置使用find(v)每個頂點的。每個新設置都是圖中的連接組件

來源

2014-01-12 18:48:52

在圖中查找連接的組件

回答

相關問題