単一ソースとシンクのDAG

Question

DAGのパスを単一のソースと単一のシンクで見つけるアルゴリズムを作成する必要があります。 DSFとトポロジカルなソートを使用しようとしましたが、何もしませんでした...） 私は誰も私のためにそれを解決するが、いくつかの指導をしたくありません。 【またグラフであるので]、また具体的にはDAGに -

は

Answer 1

BFS一般重み付けされていないグラフの最短経路を発見していただきありがとうございます。それをコード化するのも非常に簡単です。

DFSはパスを見つけることに注意してください。ただし、最短のパスである必要はありません。

また、実行後にBFSから実際のパスを取得する方法については、this postを参照してください。

編集：ご意見によると、O(|V|)解決策が必要と思われ、それは最短である必要はありません。 DFSの変更は、DAGが単一のソースと単一のシンクを持っているので、ソースからのすべてのパスがシンクに達するのでです。

グラフはDAGであるため、ソースからのすべてのパスがシンクに到達することを確認したので、特定のパスを探索して後退する必要はありません[再帰またはスタックは必要ありません]。

擬似コード：

modifiedDFS(source,target): 
    map <- new map 
    current <- source 
    while (current != target): 
    next <- current.getNextVertex() //just chose an arbitrary edge and follow it, doesn't matter which 
    map.put(next,current) //we "discovered" next by following current 
    current <- next 

このアルゴリズムを実行した後、あなたは ターゲットからソースにマップをバックに従わなければならない - あなたは[もちろん逆転]実際のパスを取得し

複雑さは確かにO(n)です。なぜなら我々は各ノードをたいてい1回訪問するからです。 O(n)を維持するためには、マップはハッシュマップでなければならず[ツリーマップではありません]。頂点が列挙されている場合、マップを配列として実装することもできます。