9

私は DAG を実装していますが、Java でそれを表す唯一の方法は次のとおりかどうか疑問に思っています。

class Node{
List<Node> parents;
List<Node> successors;
int value; }

class DAG{
Node root; // assuming only one root exists
}

親と子の 2 つのリストを持たない、より単純なものを探しています。
出来ますか？また、この表現には問題があり、特定のノード x に到達し、x からルート ノードへのパスが必要な場合、すべての親セットを経由せずにパスを見つけるにはどうすればよいでしょうか?

4

1 に答える 1

10

有向グラフの構造を単純化するために、ノードが祖先に戻るリンクを持つ必要はありません。また、Node クラスを DAG クラス内に配置します。有向グラフでは、ノード A がノード B にリンクしている場合、B から A へのパスが存在する必要がないため、概念的にはこの表現の方が理にかなっています。

public class DAG {
   Node root; // assuming only one root exists

   public static class Node{
      List<Node> successors;
      int value; 
   }
}

ルートから特定のノードへのパスを見つけるには、アルゴリズムを実行してグラフを検索する必要があります。これは、特定のノードが見つかるまで、おそらく再帰的に、グラフ内の他のノードにアクセスできることを意味します。この種の計算を繰り返さないようにしたい場合は、ルートから特定のノードへのパスを次のように保存することもできます。

class PathMap {
  HashMap<DAG.Node, List<DAG.Node> > pathMap;

  public List<DAG.Node> getPathFromRoot(DAG.Node n) {
     List<DAG.Node> pathFromRoot = pathMap.get(n);
     return pathFromRoot;
  }
}

現在、ルートから特定のノードへの複数の異なるパスが存在する場合があります。その場合、最短パス優先アルゴリズムを実装して、最適なパスを見つけて保存することをお勧めします。疑似コードについては、このdzone の記事を参照してください。

于 2013-03-17T12:54:49.840 に答える