如何查找連接的子圖？

我有一個網絡，但這個網絡沒有連接。我想知道如何在這個網絡中找到最大的連通圖？如何查找連接的子圖？

來源

2013-04-02 nasi

這與C++有什麼關係？你是否特別工作？你卡在什麼地方？請包括所有相關的細節。在目前的形式下，這個問題不夠好/不夠清楚。 – Bart

這是很不清楚你想要做什麼。另外你的問題是標籤爲C++，但你說網絡，圖形等。 – banuj

大家這是OP的第一個問題。請嘗試改進問題前downvoting並提供一些指導 –

要計算節點所屬的連接組件，只需運行任何種類的圖搜索算法，例如breadth-first search。

解決你的問題遍歷網絡中的所有節點，並執行以下操作：如果給定的節點已經被添加到一個組件進入下一個節點

（繼續循環）
如果該節點尚未被添加到組件中，運行任何圖搜索（例如，如上建議的BFS），並將所有訪問的節點標記爲屬於相同的組件。
選擇上述步驟2中構建的最大尺寸組件。

來源

2013-04-02 07:51:36

讓圖形成爲[n] [n]，如果連接了i，j，則[i] [j] = 1。

你可以做以下事情。

count=0;/global 


void dfs(int i) 
{ 

int k; 
for(k=0;k<n;k++) 
    if(A[i][k]==1 && !visited[k]) 
    { 
     count++; 
     visited[k]=1; 
     dfs(k); 
    } 
} 
for(i=0; i < n;i++) 
    { 
     if(!visited[i]) 
     { 
      count=1; 
      visited[i]=1; 
      dfs(i); 
          // map i with count .. here 

     } 
    }

所以一旦你做了節點的映射數與網絡中的其節點之一。

您現在需要做的就是在地圖中找到具有最大數量的節點。

所以你會得到的鑰匙，這是一個大型網絡節點與計數地圖（我）。

使所有節點訪問到0和應用DFS（我）再次你可以得到

整個網絡連接我和你有計數反正。

來源

2013-04-02 09:34:27 MissingNumber

另一種簡單的方法是使用union-find：

S = array filled with 1s (|V| elements) 

for each edge (u,v) in E: 
    if find_set(u) != find_set(v): 
     sum = S[find_set(u)] + S[find_set(v)] 
     S[find_set(v)] = sum 
     S[find_set(u)] = sum 
     union_set(u, v)

在結束時，S [find_set（U）]將U屬於哪個節點所連接的組件的大小。要找到最大的一個，你只需要find max（S）。

由於find_set和union_set都很容易實現（每行有兩行C++），所以我發現這種方法比DFS或BFS更清晰。

來源

2013-04-03 02:27:08

如何查找連接的子圖？

回答

相關問題