在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找到它到根节点的路径，如何在不遍历所有父节点集合的情况下实现？

- seteropere

---

看一下这个线程 https://dev59.com/kXVC5IYBdhLWcg3w7Vxq - Doron Manor

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文章以获取伪代码。

- Thorn

---

是否合理删除父节点列表取决于您的典型用例。正如Thorn所指出的那样，在原则上，您可以在DAG中删除父节点，因为它们是由子节点（或父节点）隐含给出的。然而，如果在您的应用程序中经常需要找到某个节点的一些祖先，则父节点列表可能有助于实现快速算法来执行此操作（因为您不总是需要从根开始并潜在地遍历整个图形，而是从给定节点向后移动尽可能远）。 - Frank Hopkins