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

java graph

2022-09-03 18:24:46

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

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

链表？ArrayList？地图？

哪一个更适合我的实现？

答案 1

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

adjacency list
the adjacency matrix

请参阅 http://en.wikipedia.org/wiki/Adjacency_list 和 http://en.wikipedia.org/wiki/Adjacency_matrix。
这些文章还讨论了这两种结构的优缺点。

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

  ...

}

希望这有帮助。