52

切断されたサブグラフの数が不明なグラフがあります。それらすべてを見つけるための良いアルゴリズム（またはJavaライブラリ）は何ですか？

4

8 に答える 8

66

あなたが探しているものは一般的にフラッドフィルと呼ばれていると思います。グラフをBFSまたはDFSのどちらでトラバースするかはあなた次第です。

基本的に、ラベルのない（別名、色のない）ノードを取得し、それに新しいラベルを割り当てます。そのノードに隣接するすべてのノードに同じラベルを割り当て、そのノードから到達可能なすべてのノードに同じラベルを割り当てます。

到達可能なノードにラベルを付けることができなくなったら、ラベルのない別のノードを選択して最初からやり直します。この新しいノードにラベルが付いていないという事実は、以前のノードから到達できないため、別の切断されたコンポーネントにあることを意味していることに注意してください。

ラベルのないノードがなくなると、使用する必要のある個別のラベルの数は、グラフのコンポーネントの数になります。各ノードのラベルは、どのノードがどのコンポーネントの一部であるかを示します。

于 2009-08-28T19:50:15.417 に答える
26

Javaの実装ではありませんが、おそらく誰かにとって役立つでしょう。Pythonでそれを行う方法は次のとおりです。

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph

d = list(nx.connected_components(g)) 
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

詳細はこちら。

于 2012-07-08T20:23:23.457 に答える
12

この質問には十分に説明されていない側面がたくさんあるので、やや網羅的な答えを出します。それにもかかわらず、テキストの壁を投稿する私の傾向。：/これは宿題の質問または独学の質問であると想定しているので、正直な答えを出すつもりはないことにも注意してください。

グラフの接続性を検出するための2つの基本的なアルゴリズムは、深さ優先探索と幅優先探索です。これらは本当にあなたが見たい2つの出発点です。どちらも解決策にたどり着きますが、方法は異なり、問題のかなり詳細な側面を考慮せずにどちらが「より良い」かを議論するのは困難です。しかし、先に進みましょう。

前に述べたように、あなたはいくつかの重要な詳細を省略しました、そして私はここでいくつかの可能性に触れます。

グラフは有向ですか、それとも無向ですか？そして、「強い」意味での接続性（この場合、oggyの答えを参照）、または「弱い」意味での接続性を考慮しますか？あなたの答えに応じて、あなたは微妙に異なる方法であなたのアルゴリズムにアプローチしなければならないでしょう。無向グラフの場合、弱い接続と強い接続は同等であるため、これはすばらしいことです。ただし、アルゴリズムを実装または検索するときは、グラフの構造を念頭に置く必要があります。

さらに、「サブグラフを見つける」（言い換え）とはどういう意味かという問題があります。通常、グラフの接続性は決定問題です。単に「接続されたグラフが1つある」、または「サブグラフが2つ以上ある（つまり、切断されている）」ということです。そのためのアルゴリズムを持つことは、最小限の本の仕事を必要とします、それは素晴らしいです。:)次のステップはグラフの数、文字通りグラフの数であり、その本の仕事もそれほど悪くはありません。最後に、各サブグラフのノードのリストが必要になる場合があります。最後に、サブグラフ、エッジ、およびすべてを文字通りコピーすることをお勧めします（したがって、戻りタイプはグラフのリストになり、各グラフが接続されているという暗黙の不変条件が含まれると思います）。これらの異なる結果タイプのいずれも、異なるアルゴリズムを必要としません。ブックワークへの異なるアプローチが必要です。

これらはすべて、かなり基本的な質問に対してはばかげた量のやり過ぎのように思えるかもしれませんが、このような単純なグラフの質問にも関係するすべての側面を強調したいと思いました。一種のクリフハンガーとして、これが実行時やメモリ使用量にまだ影響を与えていないことに注意してください！:)-Agor

于 2009-08-28T19:54:58.857 に答える
3

JGraphTは、LGPLライセンスの下でライセンスされている優れたオープンソースのグラフ作成ライブラリです。私は過去にそれを使用してグラフを処理し、グラフ内のサイクルを検出しました。また、かなり使いやすく、JGraphを使用してグラフを視覚化できます。

于 2009-08-28T19:49:26.103 に答える
2

私はあなたがすべての（強く）接続されたコンポーネントを見つけたいと思っていると思いますか？そのためには、Tarjanのアルゴリズム（DFSの変形）を使用できます。

于 2009-08-28T19:12:21.140 に答える
2

接続されているすべてのノードを見つけるための幅優先探索はどうですか？接続されているノードのリストを取得したら、すべてのノードのリストからこのリストを差し引きます。切断されたノードのリストが表示されます

于 2009-08-28T19:22:34.333 に答える
1

有向グラフの弱く接続されたすべてのサブグラフが必要な場合に、同様の問題が発生しました。私はここでそれについてブログを書きました。JUNG APIを使用して、2つのアプローチを比較しました。私の最初のアプローチは、問題を解決するためのテンプレートとして使用できます。

于 2010-03-08T17:23:00.340 に答える
1

私はおそらく標準的なアルゴリズムを見つけるべきでした（ウィキペディアにはいくつかの提案があります）が、私はこれを自分で思いついたので、私の目的にはうまくいきました。私のC＃実装では、40,000ノードと44,000エッジのグラフを処理して、160個のサブグラフと20,000個の未接続ノードを見つけるのに数秒かかります。HashSetを使用して各サブグラフグループを格納したため、テストグループのメンバーシップは約O（1）であり、アルゴリズム全体はO（E * C）になります。ここで、Eはエッジの数、Cはグラフ内の連結成分の数です。 。ウィキペディアは、ノード数が線形であるO（N）アルゴリズムについて言及しているので、私のものは最大限に効率的ではないと確信していますが、私のアプリケーションにとっては十分に高速でした。（編集：グループのマージのコストについても詳しく説明しているので、複雑さの分析にあまり重きを置かないでください。）

論理：

For each edge A->B
  If A is in a group and B is not, add B to group A
  If A is not in a group and B is, add A to group B
  If A and B are in different groups, merge the groups
  If neither A or B is in a group, create new group containing A and B

擬似コード：

graph = {nodes, edges}
groups = {}
foreach edge A->B in graph.edges:
    groupA = findgroup(A)
    groupB = findgroup(B)
    if (groupA && !groupB)
        groupA.add(B)
    elif (!groupA && groupB)
        groupB.add(A)
    elif (groupA && groupB)
        if (groupA != groupB)
            groupA.union(groupB)
            groups.delete(groupB)
    else
        groups.add({A,B})

findgroup(node):
    for group in groups:
        if group.contains(node):
            return group
    return null

これは、エッジに関与していないノードをキャプチャしないことに注意してください。私の特定の目的のために、これは大丈夫でした。すべての単一ノードグループを取得する場合は、最終パスを実行できます。

foreach node in graph.nodes:
    group = findgroup(node)
    if !group:
        groups.add({node})
于 2022-02-12T03:33:32.310 に答える