java - 在 Java 中实现 DAG 的不同方法

Question

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

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

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

我正在寻找更简单的没有 parent 和 child 的两个列表。
可能吗？ 另外我对这种表示有一个问题，如果我到达一个特定的节点 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;
  }
}

现在从根到给定节点可能有几条不同的路径。在这种情况下，您可能希望实现 shortest-path-first algorithm找到并存储最佳路径。看这个dzone article用于伪代码。