Java-哪个是Graph的最佳实现结构？

Question

该图非常大，但无向。边缘未加权。

在我的实现中，我必须找到最大度数的顶点，并在顶点和边上都删除。

链表？数组列表？地图？

哪种对我的实施更好？

Answer 1

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

代码，类似于以下内容：

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());
  }

  ...

}

希望这可以帮助。