次の演習が与えられました: n 個のノード (n < 1 000 000) を持つ重み付けされていない有向弱結合グラフがあります。最小数のノードから始めて、グラフ全体をトラバースしたいと考えています。問題は、どのノードからトラバーサルを開始するかです。この特定のトピックに関するコンテンツは見つかりませんでした。ただし、アルゴリズムを思い付くことができましたが、十分に効率的ではありません。
- グラフを隣接リストに保存します (n は 2 次元行列には大きすぎる可能性があります)
- 各ノード i から BFS を開始し、到達したノードを
x[i][...]
(x = List<List<int>>
)に格納します。 - あるかチェックします
x[i].Count == n
- あるかチェックします
(x[i] union x[j]).Count == n
- あるかどうかをチェックします
(x[i] union x[j] union x[k]).Count == n
...だから、x の 2、3、4... サブセットのすべての可能な和集合を作成し、そのカウントが n であるかどうかをチェックします。
n が高すぎなければ問題ありませんが、n が大きい場合はより効率的なアルゴリズムが必要です。
どんな助けでも大歓迎です(あなたは私が再び眠りにつくことができるようにするでしょう)!:)