我不能使用任何外部库,所以我试图考虑一些自己构建数据结构的方法。我在想也许是这样的:

public class Node{
    Set<Edge> adjacent;
    int value;
}

public class Edge{
    Node target;
    int weight;
}

但是我猜测可能有更好的方法来做到这一点。

该图的最终用途是在其上运行Bellman Ford算法,但显然我首先需要一个可运行的图!

最佳答案

答案很大程度上取决于您计划应用于图形的算法。

有两种常见的表示图的方式-adjacency listadjacency matrix。在您的情况下,邻接矩阵是代表权重的整数的方阵。您的表示使用邻接表。

有些算法在邻接矩阵上效果更好(例如Floyd-Warshall算法)。其他算法在邻接表上效果更好(例如Dijkstra算法)。如果您的图是稀疏的,则禁止使用邻接矩阵。

关于java - 我可以用什么方法来表示Java中的加权有向图?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13447402/

10-08 22:13
查看更多