我不能使用任何外部库,所以我试图考虑一些自己构建数据结构的方法。我在想也许是这样的:
public class Node{
Set<Edge> adjacent;
int value;
}
public class Edge{
Node target;
int weight;
}
但是我猜测可能有更好的方法来做到这一点。
该图的最终用途是在其上运行Bellman Ford算法,但显然我首先需要一个可运行的图!
最佳答案
答案很大程度上取决于您计划应用于图形的算法。
有两种常见的表示图的方式-adjacency list和adjacency matrix。在您的情况下,邻接矩阵是代表权重的整数的方阵。您的表示使用邻接表。
有些算法在邻接矩阵上效果更好(例如Floyd-Warshall算法)。其他算法在邻接表上效果更好(例如Dijkstra算法)。如果您的图是稀疏的,则禁止使用邻接矩阵。
关于java - 我可以用什么方法来表示Java中的加权有向图?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13447402/