我可以通过哪些方式在 Java 中表示加权的有向图？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13447402/
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
What are some ways I can represent a weighted, directed graph in Java?
提问by Hoser
I can't use any external libraries, so I'm trying to think of some ways to build the data structure myself. I was thinking maybe something like this:
我不能使用任何外部库，所以我试图想一些方法来自己构建数据结构。我在想也许是这样的：
public class Node{
Set<Edge> adjacent;
int value;
}
public class Edge{
Node target;
int weight;
}
But I'm guessing there's probably a better way to do it.
但我猜可能有更好的方法来做到这一点。
My eventual use for this graph is to run the Bellman Ford algorithm on it, but I obviously need a functioning graph first!
我对这个图的最终用途是在其上运行 Bellman Ford 算法，但显然我首先需要一个功能图！
回答by dasblinkenlight
The answer depends a lot on the algorithms that you are planning to apply to your graphs.
答案很大程度上取决于您计划应用于图形的算法。
There are two common ways to represent a graph - an adjacency listand an adjacency matrix. In your case, and adjacency matrix is a square array of integers representing weights. Your representation uses an adjacency list.
有两种常用的方式来表示图 -邻接表和邻接矩阵。在您的情况下，邻接矩阵是表示权重的整数方阵。您的表示使用邻接列表。
There are algorithms that work better on adjacency matrixes (e.g. Floyd-Warshall algorithm). Other algorithms work better on adjacency lists (e.g. Dijkstra's algorithm). If your graph is sparse, using adjacency matrix may be prohibitive.
有些算法在邻接矩阵上效果更好（例如 Floyd-Warshall 算法）。其他算法在邻接表上效果更好（例如 Dijkstra 算法）。如果您的图形稀疏，则使用邻接矩阵可能会令人望而却步。
回答by leo
As usual, you can represent graphs as Adjacency Lists or Adjacency Matrices. The choice really depends on the details of your problem.
像往常一样，您可以将图形表示为邻接列表或邻接矩阵。选择实际上取决于您的问题的详细信息。
Using an Adjacency Matrix, you could simply have a matrix of integers, representing the weight.
使用邻接矩阵，您可以简单地拥有一个表示权重的整数矩阵。
If you decide to have an Adjacency List, you could simply store a list of list of integers (assuming the nodes of your graph are identified by an integer value), similar to what you've done.
如果您决定拥有一个邻接列表，您可以简单地存储一个整数列表列表（假设您的图的节点由一个整数值标识），类似于您所做的。
回答by Sumit
You can use a node as in an unweighted graph, holding a list of nodes to which it is connected,and additionally add the weights associated with the connections as:
您可以像在未加权图中一样使用节点，保存它所连接的节点列表，并另外添加与连接关联的权重，如下所示：
public class Node{
int value;
HashMap<Node,Integer> adjacency;
}
