0

次の演習が与えられました: 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 が大きい場合はより効率的なアルゴリズムが必要です。

どんな助けでも大歓迎です（あなたは私が再び眠りにつくことができるようにするでしょう）！:)

4

1 に答える 1

0

入力エッジを持たないノードを見つけます。これらのノードをループし、ノード v ごとにグラフのトラバースを開始します。アクセスしたノードを覚えておいてください (それらをハッシュ テーブルに入れるか、それらをマークしてください)。すでに訪れたノードに到達したら、トラバースを停止します。

各ノードに着信エッジのリストと発信エッジのリストがある隣接リスト表現が必要になります。次に、次のようにします。

Set nodesToVisit = emptySet;
for i=1 to n:
    if incoming[i].size() == 0:
        nodesToVisit.add(i)

Set visited = emptySet;
for v in nodesToVisit:
    nodesToVisit.remove(v)
    if(v is not in visited):
        visit(v);
        visited.add(v);
        for u in outgoing[v]:
            nodesToVisit.add(u)
于 2013-03-29T00:41:51.210 に答える