Java邻接表实现的带有向加权边的图

Question

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

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

Answer 1

你应该将你的图形表示为HashMap，其中key是顶点的标签，value是顶点对象。

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

Vertex是一个封装顶点属性的类。将有一个HashMap属性用于相邻的具有权重的顶点。

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

你可以通过顶点类给你的图形添加更多的功能和属性。