0

たとえば、頂点とエッジのリストがそれぞれあるグラフオブジェクトがあります。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を使用してグラフをトラバースすることに関連していますか？これを通して私を助けてください、ありがとう。

4

4 に答える 4

1
  1. 開始点として1つの頂点を取ります
  2. そのバーティクルからBFS/DFSを起動します
  3. すべてのバーティクルが訪問されたかどうかを確認します
于 2012-09-10T09:50:30.930 に答える
1

はい、問題はBFS/DFSを使用して解決できます。これら2つと開始ノードから任意の検索アルゴリズムを選択できます。検索手法（DFSまたはBFS）で少なくとも1つのノードに到達しない場合は、1つ以上の切断されたコンポーネントと、いくつかの個別のノードまたは相互接続されたノードがあることを意味します。孤立しています。ただし、これは、切断されたコンポーネントがいくつ存在するかを示しているわけではありません。このため、他の訪問されていないノードを使用してトラバーサルを再度開始する必要があります。

于 2012-09-10T10:45:48.937 に答える
0

スパニングツリーを使用しても、この結果を得ることができます。ウィキでは、次のように定義されています。

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.

スパニングツリー

図：スパニングツリー（出典：ウィキペディア）

最小スパニングツリー を見つけたい場合は、プリムのアルゴリズムが適しています。コードスニペットの例：

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

アップデート：

プリムのアルゴリズムの説明はここにあります。

最小スパニングツリーの詳細については、こちらをご覧ください。

于 2012-09-10T09:22:48.123 に答える
0

Pythonでグラフの連結成分をカウントするためのアルゴリズムで、同様の質問に回答しました。

グラフが接続されているかどうかを確認するため、スクリプトに次の関数を追加します。

def isGraphConnected(graph):
    return get_connected_components_number(graph)==1
于 2012-09-10T09:52:30.387 に答える