java - 有向グラフの穴を見つける方法は?

Question

質問 : 有向グラフがあります。時間計算量 Ɵ(n) でグラフの穴 (ピット) を見つける方法。

グラフの穴 : (入力) が n-1 次、(出力) が 0 次の頂点の場合、グラフに穴があります。

Answer 1

何か不足していますか？グラフのエッジに沿ってグラフを検索しないでください。グラフ内の n 個の頂点すべてを反復処理し、それぞれの入力エッジと出力エッジの数をテストします。頂点ごとに、着信エッジと発信エッジの数を保存できると思います。エッジ数がある場合、これは O(n) をスケーリングします。

@REPLY: より具体的にするには、グラフがどのように実装されているかを知る必要があります。しかし、私は次のようなことを意味します：

foreach( node in graph )
     if (( node.numberInputEdges == numNodes -1 ) && 
         ( node.numberOutputEdges == 0 ))
         print ( "this node is a pit" )

Answer 2

グラフには 1 つの「ピット」しか存在できません (deg_in = N-1 のため)。したがって、deg_out = 0 のすべてのノードを検索します。2 つの場合は停止します。ある場合は、deg_in を確認します。これがO(N)です。

Answer 3

隣接リストの実装がある場合は、それをスキャンするだけで、出次数が 0 の頂点があれば O(n) 時間で見つかります。隣接行列がある場合は、DFS を使用できます。

DFS では、発信ノードが見つかるたびにカウンターをインクリメントするだけです。

擬似コード:

for each adjacent node :
   indegree->neighbour ++;
   if (neighbour not visited ) dfs(neighbour)   

最後に indegree 配列をスキャンして、indegree (n-1) を持つノードを取得します。bcoz すべてのノードが Pit へのエッジを持ちます。