覆蓋率在數據結構

說，我分別具有頂點和邊的列表中的圖形對象的曲線圖的所有節點。 G = {V，E}覆蓋率在數據結構

G={[3, 4, 1, 2, 5, 6],[3->4, 1->2, 1->5, 5->4, 5->6]}

假設圖是unweighted and undirected我在需要找到是否所有Vertices are interconnected with eachother即，沒有單獨的節點或相互連接的節點是分離的。

1 -- 2 

| 

5 -- 4 -- 3 

| 

6

它與使用DFS或BFS遍歷圖相關嗎？請幫助我解決這個問題，謝謝。

來源

2012-09-10 Logan

如果是無向圖，DFS/BFS會給你從一個給定的起始節點到達的所有節點。在此運行期間未訪問的節點未連接到此組件。讀wiki頁面約[連接的組件（http://en.wikipedia.org/wiki/Connected_component_（graph_theory））的更多信息。 – Baz

可以實現使用spanning tree也是這個結果。在維基它被定義爲：

In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some (or perhaps all) of the edges of G.

SPanning Tree

圖：生成樹（來源：wikipedia）

如果你想找到minimum spanning tree Prim's algorithm可以是一個很好的選擇。代碼段的示例：

MST-Prim(G,r) 
01 for each vertex u element of G.V 
02 u.key :=infinity 
03 u.parent := NIL 
04 r.key := 0 
05 init(Q, G.V) // Q is a priority queue 
06 while not isEmpty(Q) 
07 u := extractMin(Q) // add u to T 
08 for each v element of u.adj do 
09  if v element of Q and w(u,v) < v.key then 
10  v.key := w(u,v) 
11   modifyKey(Q,v) 
12   v.parent := u

UPDATE：

Prim算法的說明可發現here。

約最小生成樹的更多信息請here。

來源

2012-09-10 09:22:48

如果OP只想檢查圖形是否連接，那麼這不是很複雜嗎？ – Baz

@Baz yup，那是真的。但它是此目的最流行的算法之一。遲早，如果他/她想編寫圖形問題，人們必須學習這一點。 –

連通圖G的生成樹也可以定義爲G的邊的最大集合，它不包含循環，或者'作爲連接所有頂點的最小邊集合.- [生成樹]（http：// en.wikipedia.org/wiki/Spanning_tree）所以這實際上是OP問題的有效答案。 –

以一個verticle爲起點
啓動BFS/DFS從verticle
檢查所有verticles進行了走訪

來源

2012-09-10 09:50:30 Ari

一個simmilar問題已Algorithm for counting connected components of a graph in Python有了答案。

既然你是問，如果圖是連通的，你添加的功能的腳本：

def isGraphConnected(graph): 
    return get_connected_components_number(graph)==1

來源

2012-09-10 09:52:30 Nejc

OP是針對java。 – Baz

他的問題更多的是關於實現的想法，而不是實際的實現。該代碼可以很容易地轉移到Java。 – Nejc

是的，如果你理解python :)我不會假設這一般。 – Baz

是，這個問題可以通過BFS/DFS來解決。您可以在這兩個和任意起始節點之間選擇任何搜索算法，並且如果通過搜索技術（DFS或BFS）您沒有到達至少一個節點，這意味着有一個或多個斷開連接的組件和某些單個節點或互連節點被隔離。但是這並沒有告訴你有多少斷開的組件存在，因此你必須再次使用其他一些非訪問節點來啓動遍歷。

來源

2012-09-10 10:45:48

覆蓋率在數據結構

回答

相關問題