函數確定連通性

Question

假設有n不同點P1, P2,...,Pn。

定義連通性矩陣M=(c_ij)爲大小爲n的方陣。 c_ij將給true如果i=j或有點Pi和Pj之間的線段。

如果任意兩點之間存在至少一條路徑（一組線段），則連接一組點。我們把連接點集稱爲適當的圖。一個點本身可以​​是一個適當的圖。

當沒有從第一個圖中的任何點連接到第二個圖中的任何點時，兩個適當的圖斷開連接。

連通性定義爲不連通的適當圖的數量。

例如，

 P1 P2 P3 P4 P5 
P1 true false true false false 
P2 false true false false false 
P3 true false true false true 
P4 false false false true true 
P5 false false true true true 

具有兩個斷開適當的曲線圖，即P2和{P1,P3,P4,P5}。

我的問題是如何編寫一個函數來接入連通性矩陣並返回一個斷開連接的適當圖表的列表。例如，上面的例子應該返回list(list(1,3,4,5),list(2))。

Answer 1

您正在尋找圖形的連接組件。

不幸的是，像這樣的鄰接矩陣是非常不理想的，因爲你不能比O（n^2）快。在下文中，我將介紹可以使用的兩種解決方案。如果直接訪問鄰居，第一種情況會更好，如果直接訪問邊緣，第二種情況會更好。這些都不適用於您的場景。這兩種解決方案的時間複雜度對於鄰接矩陣是相等的。所以你必須測量，哪一個實際上更快。

如果您有一個數據結構可讓您直接訪問鄰居，則可以使用BFS或DFS來獲取連接的組件。該方法在this answer中描述。請注意，此答案中陳述的時間複雜性不適用於您的場景。您可以使用union-find data structure。然後，您可以執行以下操作：

Initialize union-find uf with n entries 
for every edge (i, j) 
    uf.union(i, j) 
next 
initialize map int -> list of vertices 
for every vertex v 
    p <- uf.representative(v) 
    map[p].insert(v) 
next 

地圖中的列表就是連接的組件。