有哪些方法可以代表Java中的加权有向图？

Question

我不能使用任何外部库,所以我试着想一些自己构建数据结构的方法.我想的可能是这样的:

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

public class Edge{
    Node target;
    int weight;
}

但我猜这可能是一种更好的方法.

我最终使用这个图是在它上运行Bellman Ford算法,但我显然首先需要一个功能图!

Answer 1

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

表示图形有两种常用方法 - 邻接列表和邻接矩阵.在您的情况下,邻接矩阵是表示权重的整数的正方形数组.您的表示使用邻接列表.

有些算法在邻接矩阵上运行得更好(例如Floyd-Warshall算法).其他算法在邻接列表上更好(例如Dijkstra算法).如果图形稀疏,则使用邻接矩阵可能会令人望而却步.