Java - 哪个是Graph的最佳实现结构？ [英] Java - Which is the best implementation structure for Graph?

问题描述

图表非常大，但无向。

在我的实现中，我必须找到具有最大度数的顶点，并在顶点和边上进行删除操作。

链接列表？数组列表？ Map？

哪一个更适合我的实现？

解决方案

我的建议是将顶点存储在优先队列中。这样，您可以非常快速地访问最高度的顶点。至于如何实现顶点，我会将每个相邻顶点存储在某种集合数据结构（如HashSet或TreeSet）中，以便能够高效地移除东西。我不会明确表示边缘，它不是必需的。

代码，类似于：

  class Graph {
 
 PriorityQueue< Vertex>顶点; 
 $ b public graph（）{
 vertexes = new PriorityQueue< Vertex>（10，new Vertex（））; 
} 
 
 public Vertex maxDegreeVertex（）{
 return vertexes.peek（）; 
} 
 
 ... 
 
} 
 
类Vertex实现了Comparator< Vertex> {
 HashSet< Vertex>边缘; 
 
 public Vertex（）{
 edges = new HashSet< Vertex>（）; 
 
 
 public compare（Vertex v1，Vertex v2）{
 v2.edges.size（）。compareTo（v1.edges.size（））; 
} 
 
 ... 
 
} 
  

希望这会有所帮助。

The graph is very large but undirected. Edges are unweighted.

In my implementation, I have to find the vertex with max degree and do deletion on both vertexes and edges.

Linked list? ArrayList? Map?

Which one is better for my implementation?

解决方案

My suggestion would be to store the vertexes in a priority queue. That way you can have very fast access to the vertex with the highest degree. As for how to implement the vertexes, I would store each neighboring vertex in some kind of set data-structure such as a HashSet or a TreeSet to be able to remove stuff efficiently. I wouldn't represent the edges explicitly, it's not needed.

Code, something along the lines of:

class Graph {

  PriorityQueue<Vertex> vertexes;

  public Graph() {
    vertexes = new PriorityQueue<Vertex>(10,new Vertex());
  }

  public Vertex maxDegreeVertex() {
    return vertexes.peek();
  }

  ...

}

class Vertex implements Comparator<Vertex> {
  HashSet<Vertex> edges;

  public Vertex() {
    edges = new HashSet<Vertex>();
  }

  public compare(Vertex v1, Vertex v2) {
    v2.edges.size().compareTo(v1.edges.size());
  }

  ...

}

Hope this helps.

这篇关于Java - 哪个是Graph的最佳实现结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！