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

Question

该图非常大，但是不带方向，边不带权重。

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

链表？ArrayList？Map？

哪一个更适合我的实现？

- user236691

Answer 1

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

• 邻接表

• 邻接矩阵

请参考http://en.wikipedia.org/wiki/Adjacency_list和http://en.wikipedia.org/wiki/Adjacency_matrix了解这两种结构的优缺点。

- Chris

---

我的数据结构书建议使用邻接映射，它是邻接表的一个变种，其中次要列表被替换为映射。这可以减少某些方法的预期运行时间。（《Java数据结构与算法》Goodrich、Tamassia和Goldwasser著） - Fr4nc3sc0NL

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

  ...

}

希望这可以帮助到您。

- svenningsson

---

谢谢代码。 我以前从未使用过PriorityQueue，删除操作容易吗？ - user236691

没错，这很简单。如果你想在检索的同时删除具有最高优先级的元素，只需使用poll方法即可。通常情况下，使用remove方法来删除元素。只需在谷歌上搜索“priority queue java”以获取文档。 - svenningsson

明白了，谢谢！ 还有一个问题，为什么要在顶点类中放置比较方法(compare method)的目的是什么？ - user236691

哦，我想这有点像是一个hack，但它使实现比较方法更容易。我想将自己定制的比较器提供给优先队列。为了实现它，我需要访问顶点的邻居数量。由于我不想在代码片段中添加那种东西，所以我只是将比较方法放在了Vertex类中。但你最好在其他地方实现它，也许是在创建PriorityQueue时创建匿名类。 希望这可以帮到你。祝你好运！ - svenningsson

Vertex 应该实现 Comparable 而不是 Comparator，来定义自然顺序。这样你就不必指定比较器了。 - Christoffer Hammarström

每次删除顶点都是O(n)，这不会很慢吗？如果要在固定优先级的约束条件下实现删除边，该怎么做呢？ - Piyush Ahuja

Answer 3

根据上述建议，答案应该是

使用LinkedList的Map...

你的数据结构可以像这样（根据你的要求而变化）...

Map<?, List<?>>
<Node-name, List-of-nodes-connected-to-it>

基本上，图最好使用哈希实现，上述数据结构在此方面非常有帮助。

- Rites

---

这不是事实，哈希并非总是最佳选择，有时邻接矩阵才是最好的结构。这取决于算法。 - Nick Fortescue

此外，并非所有的映射都使用哈希表，例如TreeMap就不是。 - Nick Fortescue

“depends on the algorithm”是什么意思？能举个例子吗？ - user236691

任何算法都有一个关键的阶段，即查找两个顶点是否相邻。在矩阵中为O(1)，在列表中为O(min(A,B))，其中A和B是顶点的度数。 - Nick Fortescue

Answer 4

图的实现取决于你要做什么。但对于大多数情况，基于邻接列表的实现是有帮助的。

在Java中，你可以使用Map<>来实现它。这里是我博客上通用的基于邻接列表的Graph.Java实现。

- rai.skumar

Answer 5

如果您的算法需要查找最大度数，则需要一个按度数排序的数据结构，例如优先队列。

然后您需要存储图本身。为了快速删除，我建议使用类似于稀疏数组结构的东西。如果您必须使用java.util数据结构，则从顶点到连接顶点列表的HashMap提供O(1)删除。

如果您可以使用第三方库，则有这里的答案列表，其中JGraph和JUNG似乎最受欢迎。

- Nick Fortescue

Answer 6

    public class Graph {
    private Set<Vertex>vertices;
    private Set<Edge>edges;
    private Map<Vertex,List<Edge>>adj;
    // Getter setter



    public Graph(Set<Vertex> vertices, Set<Edge> edges, Map<Vertex, List<Edge>> adj) {
        super();
        this.vertices = vertices;
        this.edges = edges;
        this.adj = adj;
    }
}

// Vertex class
public class Vertex {
    private String name;

    public Vertex(String name) {
        super();
        this.name = name;
    }


}

// Edge class 

public class Edge {
    private Vertex from;
    private Vertex to;
    private int weight;

    public Edge(Vertex from, Vertex to,int weight) {
        super();
        this.from = from;
        this.to = to;
        this.weight = weight;
    }


}

// Driver class 

import java.util.HashSet;
import java.util.Set;

public class Test {
    public static void  main(String[]args) {
        Graph gr = new Graph();
        Vertex a = new Vertex("a");
        Vertex b = new Vertex("b");
        Vertex c = new Vertex("c");
        Vertex d = new Vertex("d");
        Vertex e = new Vertex("e");
        Vertex f = new Vertex("f");
        Vertex g = new Vertex("g");


        Set<Vertex>vertices = gr.getVertices();
        if(vertices == null){
            vertices  = new HashSet<>();
            vertices.add(a);
            vertices.add(b);
            vertices.add(c);
            vertices.add(d);
            vertices.add(e);
            vertices.add(f);
            vertices.add(g);
        }

        Edge ae = new Edge(a, e, 3);        
        Edge ac = new Edge(a, c, 1);
        Edge cf = new Edge(c, f, 9);
        Edge cd = new Edge(c, d, 4);
        Edge eb = new Edge(e, b, 2);
        Edge bd = new Edge(b, d, 5);
        Edge df = new Edge(d, f, 7);

    Set<Edge>edges = gr.getEdges();
    if(edges == null){
        edges = new HashSet<Edge>();
        edges.add(ae);
        edges.add(ac);
        edges.add(cf);
        edges.add(cd);
        edges.add(eb);
        edges.add(bd);
        edges.add(bd);
    }
        gr.setVertices(vertices);
        gr.setEdges(edges);

    }

}

- Kuldeep Singh

Answer 7

这取决于您还有什么其他要求。一个天真、简单的方法可能是

class Node
{
  List<Node> edges;
  int id;
}

在图中，您可能会有所有节点的列表。问题是这可能会变得不一致；例如，节点A可能在节点B的边缘列表中，但节点B可能不在节点A的列表中。为了解决这个问题，您可以将其建模如下：

class Edge
{
  Node incidentA;
  Node incidentB;
}

class Node
{
  int id;
}

同样，您将拥有系统中所有边缘和节点的列表和列表。当然，分析这个数据结构的方式与其他方法完全不同。

- G-Wiz

Answer 8

你也可以看看专门设计的库，比如JUNG

- Valentin Rocher