java - 有哪些方法可以在 Java 中表示加权有向图？

Question

我不能使用任何外部库，所以我正在尝试自己构建数据结构的一些方法。我在想也许是这样的：

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

public class Edge{
    Node target;
    int weight;
}

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

我对该图的最终用途是在其上运行 Bellman Ford 算法，但我显然首先需要一个功能图！

Answer 1

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

有两种常用的方法来表示图 -邻接表和邻接矩阵。在您的情况下，邻接矩阵是表示权重的整数方阵。您的表示使用邻接列表。

有些算法在邻接矩阵上效果更好（例如 Floyd-Warshall 算法）。其他算法在邻接列表上工作得更好（例如 Dijkstra 算法）。如果您的图是稀疏的，则使用邻接矩阵可能会令人望而却步。

Answer 2

像往常一样，您可以将图形表示为邻接列表或邻接矩阵。选择实际上取决于您的问题的细节。

使用邻接矩阵，您可以简单地拥有一个整数矩阵，表示权重。

如果您决定拥有一个邻接列表，您可以简单地存储一个整数列表（假设您的图形的节点由一个整数值标识），类似于您所做的。

Answer 3

您可以在未加权图中使用节点，保存与其连接的节点列表，并另外添加与连接关联的权重：

public class Node{
    int value;
    HashMap<Node,Integer> adjacency;
}