Java - Graph的最佳实现结构是什么？

Question

该图非常大但无向.边缘没有加权.

在我的实现中,我必须找到具有最大度数的顶点并在顶点和边上执行删除.

链接列表？数组列表？地图？

哪一个更适合我的实施？

Answer 1

表示图形的两个基本数据结构是

• adjacency list

• the adjacency matrix

请参阅http://en.wikipedia.org/wiki/Adjacency_list和http://en.wikipedia.org/wiki/Adjacency_matrix.
文章还讨论了这两种结构的利弊.

Answer 2

我的建议是将顶点存储在优先级队列中.这样,您可以非常快速地访问具有最高程度的顶点.至于如何实现顶点,我会将每个相邻顶点存储在某种集合数据结构中,例如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());
  }

  ...

}

希望这可以帮助.