Java Webアプリケーションの指向非循環グラフトラバーサル

Question

私はノードが何らかの操作を表し、エッジがそれらの操作間のデータフローを表す有向グラフを構築できるWebアプリケーションを構築しています。だからエッジ{u、v}に対しては、vがする前に実行しなければなりません。 Click this link to see a sample graph

STARTノードは初期値を表し、出力を除く他のノードは指定されたとおりに動作します。出力ノードは、入力として受け取った値を出力します。

私はそのようなグラフを処理するためにどのアルゴリズムアプローチを使用すべきですか？

Answer 1

これはトポロジカルソートの完全な例です。トラバース経由で注文要件に従ったセットを作成する最も一般的なアルゴリズムはKahn's Algorithmです。擬似コードは以下の通りで、Wikipediaのリンクにある情報は、あなたを始めるのに十分なはずです。

L ← Empty list that will contain the sorted elements 
S ← Set of all nodes with no incoming edges 
while S is non-empty do 
    remove a node n from S 
    add n to tail of L 
    for each node m with an edge e from n to m do 
     remove edge e from the graph 
     if m has no other incoming edges then 
      insert m into S 
if graph has edges then 
    return error (graph has at least one cycle) 
else 
    return L (a topologically sorted order) 

「開始ノード」は、グラフの入ってくるエッジを適切に表すことによって強制されます。開始するのはSの唯一のノードになります。他の情報をご希望の場合は、コメントに私にお知らせください。