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

Question

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

我想重量添加到每个边缘，我想通过在LinkedList增加的重量标签，每个successor对象这样做的，而且我想每Vertex添加其他变量，以备将来使用。如果我想这样做，我将不得不为顶点创建一个新的数据结构，并将一个单独的一个作为邻接列表。将两者结合为一个单一的数据结构将会是一个有效的设计？

Answer 1

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

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

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

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

您可以通过顶点类向图中添加更多功能和属性。