在 Java 中实现 DAG 的不同方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15460661/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Different ways to implement DAGs in java
提问by seteropere
I am implementing DAG and wondering whether the following is the only way to represent it in Java:
我正在实现 DAG 并想知道以下是否是在 Java 中表示它的唯一方法：
class Node{
List<Node> parents;
List<Node> successors;
int value; }
class DAG{
Node root; // assuming only one root exists
}
I am looking for something simpler without two lists for parents and children.
is it possible?
Also I have an issue with this representation that if I reached a particular node x and wanted the path from x to the root node, how I can find it without going through all the parents set?
我正在寻找更简单的东西，没有父母和孩子的两个列表。
是否可以？我也有这个表示的问题，如果我到达一个特定的节点 x 并想要从 x 到根节点的路径，我如何在不经过所有父节点的情况下找到它？
回答by Thorn
To simplify your directed graph structure, it is not necessary for nodes to have links back to their ancestors. I would also place the Node class inside your DAG class. Conceptually this representation makes more sense anyway since in a directed graph, if node A links to node B, there need not be a path from B to A. In fact there cannot be a path in both directions because that would be a cycle.
为了简化您的有向图结构，节点没有必要具有返回其祖先的链接。我还会将 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;
}
}
To find the path from the root to a particular node, you would need to run an algorithm to search through the graph. That does mean possible visiting the other nodes in the graph, probably recursively, until you locate the given node. If you want to avoid repeating these sorts of calculations, you could also store the path from the root to a given node with something like this:
要找到从根到特定节点的路径，您需要运行算法来搜索图形。这确实意味着可以访问图中的其他节点，可能是递归的，直到您找到给定的节点。如果您想避免重复这些类型的计算，您还可以使用以下内容存储从根到给定节点的路径：
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;
}
}
Now there may be several different paths from the root to a given node. In that case, you may want to implement a shortest-path-first algorithmto find and store the optimal path. See this dzone articlefor pseudocode.
现在从根到给定节点可能有几条不同的路径。在这种情况下，您可能希望实现最短路径优先算法来查找和存储最佳路径。有关伪代码，请参阅此dzone 文章。
