在java中实现DAG的不同方法

Question

我正在实现DAG,并想知道以下是否是用Java表示它的唯一方法:

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

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

我正在寻找更简单的东西,没有两个父母和孩子的名单.
可能吗？此外,我有一个问题,如果我到达一个特定的节点x,并希望从x到根节点的路径,我怎么能找到它而不经过所有父节点设置？

Answer 1

为了简化有向图结构,节点没有必要将链接返回到它们的祖先.我还将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文章.