9

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

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

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

我正在寻找没有两个父母和孩子名单的更简单的东西。
是否可以？另外我对这种表示有一个问题，如果我到达一个特定的节点 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 回答