algorithm - 有向非巡回グラフでのシンクの検出

Question

DAG：に次のプロパティを持つ頂点が1つあるとしましょう。

1. すべての頂点がそれに接続されています

2. どの頂点にも接続されていません

これは通常、シンク頂点と呼ばれます。

でこの頂点を検出することは可能ですか？グラフの頂点の数はO(n)どこですか？n

Answer 1

グラフにはサイクルがなく、すべての頂点がシンクに接続しているため、開始ノードを選択してランダムに歩き始めます。歩き続けることができないときは、せいぜいn歩で流しにいます。

nステップ（またはそれ以下で続行できません）を歩いたら、問題はシンクがあることを保証するものではないため、シンクがあるかどうかを確認する必要があります。それは別のを追加しますO(n)。だから問題はO(2 n) = O(n)

Answer 2

私が考えることができる最高のものは、O(n + m)それがであるO(n)かどうかmですO(n)。

シンクが存在すると仮定して、グラフのトポロジカルソートを実行します。ソートの最小ノードはシンクです。トポロジカルソートは。であることに注意してくださいO(n + m)。

私は以前、この問題のために簡単に変更できる実装をここに提供しました。

Answer 3

線形時間でノードに出入りするエッジの数を数えることができれば、それは可能です。まず、出力エッジがない頂点を見つけます（すべてのノードをスキャンするにはO（n））。そのような頂点が1つだけある場合にのみ、条件が満たされます。次に、入力エッジをカウントします（O（n）を使用して、すべての入力エッジをスキャンします）。正確にn-1個の入力エッジがある場合、条件は満たされます。いずれかのテストが失敗した場合、シンク頂点はありません。

「接続されている」とは、「パスで到達可能」ではなく、「エッジで接続されている」という意味だと思います。