Java邻接表实现有向加权图

Question

我正在尝试使用邻接表在Java中实现有向加权边图。它由一个大小等于顶点数的数组组成，数组的每个条目都是每个特定Vertex的后继者的LinkedList。

我想为每条边添加权重，我正在考虑通过为 LinkedList 中的每个 successor 对象添加权重标签来实现此目的，此外我想添加每个Vertex的其他变量以供将来使用。如果我想这样做，我必须为顶点创建一个新的数据结构，并创建一个单独的数据结构作为邻接列表。将两者组合为单个数据结构的有效设计是什么？

Answer 1

您应该将图形表示为 HashMap，其中键是顶点标签，值是顶点对象。

HashMap<String,Vertex> graph = new HashMap<String,Vertex>();

Vertex是封装顶点属性的类，相邻顶点都会有一个带有权值的属性HashMap。

HashMap<Vertex,Integer> adjListWithWeights = new HashMap<Vertex,Integer>();

您可以通过 Vertex 类向图表添加更多功能和属性。