对象和指针
这些只是 hammar 在另一个答案中所说的基本数据结构,Java
您可以用边和顶点等类来表示它。例如,一条边连接两个顶点,可以是有向的或无向的,它可以包含一个权重。一个顶点可以有一个 ID、名称等。大多数情况下,它们都有额外的属性。所以你可以用它们来构建你的图表,比如
Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30
这种方法通常用于面向对象的实现,因为它对于面向对象的用户来说更具可读性和方便性;)。
矩阵
矩阵只是一个简单的二维数组。假设您有可以表示为 int 数组的顶点 ID,如下所示:
int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1
这通常用于需要索引访问的密集图。你可以用它来表示一个无向/有向和加权的结构。
邻接表
这只是一个简单的数据结构组合,我通常使用HashMap<Vertex, List<Vertex>>
. 类似使用的可以是HashMultimap
Guava 中的。
这种方法很酷,因为您有 O(1)(摊销)顶点查找,它会返回我要求的这个特定顶点的所有相邻顶点的列表。
ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3
这用于表示稀疏图,如果你在谷歌申请,你应该知道 webgraph 是稀疏的。您可以使用BigTable以更具可扩展性的方式处理它们。
哦,顺便说一句,这是这篇文章的一个很好的总结,里面有精美的图片;)