大きなグラフの k サイズのサブグラフを見つけるアルゴリズムが必要です。あなたの提案は何ですか？
注: 私のグラフは無向です。
前もって感謝します。
質問する
964 次
2 に答える
0
これを行うための非常に簡単な方法は、K 反復に対してBFSまたはDFSを実行することです。
于 2012-06-17T19:12:23.363 に答える
0
大きなグラフから任意の k 個の頂点を選択すると、それらの頂点とそれらを接続するエッジ (存在する場合) のみを選択してサブグラフを作成できます。
k個の頂点を接続したい場合は、大きなグラフの接続されたコンポーネントからk個の接続された頂点を選択できます - http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29を参照してください
実際に k 個の頂点が必要で、各頂点がそれを他の k-1 個の頂点のそれぞれにリンクするエッジを持っている場合、これがクリークと呼ばれることを知る必要があり、これを見つけるのは難しい問題です - http://を参照してくださいen.wikipedia.org/wiki/Clique_%28graph_theory%29
于 2012-06-17T15:41:35.053 に答える