2

順序付けられたグラフの隣接行列があり、他のすべてがエッジを持つ頂点を見つける必要があります (その行には、対角線を除いてすべて 1 があります)。

これが隣接行列の場合:

0 0 0
0 0 0
1 1 0

アルゴリズムは頂点 3 を生成する必要があります。

このような頂点が少なくとも 1 つあるとします。

O(N^2) (N は頂点の数) での解は自明ですが、O(N) でこれを行うにはどうすればよいでしょうか?

4

2 に答える 2

0

順序付けられたグラフは、その頂点に合計順序があるグラフです。他の要件はありません。特に、エッジの移動先を制限するものではありません。したがって、質問に対する答えは、O(N^2) よりもうまくできない場合があるということです: 1 つの行にすべての非対角エントリが 1 に等しく、他のすべての行にちょうど 1 つのゼロの非対角エントリがある隣接行列を考えてみましょう。非常に幸運でない限り、隣接行列のほぼ全体を調べて、どの行に非対角ゼロがないかを調べる必要があります。

したがって、トポロジー順序を認める有向グラフを意味していると思います。つまり、有向非巡回グラフ(DAG) です。その場合、セバスチャンはすでに回答していますが、回答が受け入れられないため、できればより明確に説明してみましょう。

DAG の頂点に 1 つおきの頂点からの入力エッジがある場合、これらは長さ 2 のサイクルを形成するため、出力エッジはありません。つまり、対応する列にはゼロしかありません。このような頂点はユニバーサル シンクと呼ばれ、それを見つけるためのよく知られた O(N) アルゴリズムがあります。

一般的なアルゴリズム:

  1. 候補:= {0,1,...,N-1}
  2. |候補者|ながら > 1 :
    • 候補 u と v を任意に選択する
    • (u,v) がエッジの場合、候補から u を削除します。そうでない場合は、候補から v を削除します
  3. 最後に残った候補がユニバーサル シンクかどうかをテストする

グラフにユニバーサル シンクがあることがわかっている場合、最後の手順は不要です。

while ループの反復回数は N-1 です。これは、反復ごとに候補のセットから 1 つの頂点が削除されるためです。ユニバーサル シンクにできない頂点のみを削除するため、このアルゴリズムは正しいです。削除された頂点に出力エッジがあるか、一部の頂点からの入力エッジがないかのいずれかです。

以下のコードでは、候補のリストを明示的に保持していないことがわかります。for サイクルのステップiの候補のリストは{candidate, i, i+1, ..., N-1}であり、選択された候補uとvは候補とiです。

// step 2
int candidate = 0;
for(int i=1; i<N; i++)
{
  if(edge[candidate][i] == 1)
      candidate = i;
}
// step 3
bool no_sink = false;
for(int i=0; i<N; i++)
{
  if(candidate  != i && (edge[candidate][i] == 1 || edge[i][candidate]==0))
      no_sink = true; 
}
if(no_sink)
    printf("No universal sink.");
else
    printf("The universal sink is %d.", candidate);
于 2013-09-05T08:36:53.503 に答える