Java - Graph 的最佳实现结构是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1945099/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java - Which is the best implementation structure for Graph?
提问by user236691
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?
哪一个更适合我的实施？
采纳答案by svenningsson
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.
我的建议是将顶点存储在优先级队列中。这样您就可以非常快速地访问具有最高度数的顶点。至于如何实现顶点，我会将每个相邻顶点存储在某种集合数据结构中，例如 HashSet 或 TreeSet，以便能够有效地删除内容。我不会明确表示边缘，它不需要。
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.
希望这可以帮助。
回答by Rites
From the above suggested the answer would be
从上面建议的答案是
Map with LinkedList...
使用 LinkedList 映射...
Your datastructure could be like this(varies according to your requirement)...
您的数据结构可能是这样的（根据您的要求而有所不同）...
Map<?, List<?>>
<Node-name, List-of-nodes-connected-to-it>
Basically, Graphs are best implemented with the help of HASHING and the above datastructure helps a lot in that..
基本上，图表最好在散列的帮助下实现，上面的数据结构在这方面有很大帮助..
回答by Valentin Rocher
回答by Nick Fortescue
If your algorithm requires looking up on max degree, then you want a data structure ordered by degree, something like a PriorityQueue would be good.
如果您的算法需要查找最大度数，那么您需要按度数排序的数据结构，像 PriorityQueue 这样的东西会很好。
Then you need to store the graph itself. For deletion quickly I'd recommend something like a Sparse Array structure. If you have to use java.util data structures, then a HashMapfrom vertexes to the list of connected vertexes offers O(1) deletion.
然后您需要存储图形本身。为了快速删除，我建议使用稀疏数组结构之类的东西。如果您必须使用 java.util 数据结构，HashMap则从顶点到连接顶点列表提供 O(1) 删除。
If you could use 3rd party libraries, then there are a list of answers hereof which JGraph and JUNG seem most popular.
如果您可以使用 3rd 方库，那么这里有一个答案列表，其中 JGraph 和 JUNG 似乎最受欢迎。
回答by Chris
The two fundamental data structures for representing graphs are the
表示图的两种基本数据结构是
adjacency listthe adjacency matrix
adjacency listthe adjacency matrix
see http://en.wikipedia.org/wiki/Adjacency_listand http://en.wikipedia.org/wiki/Adjacency_matrix.
The articles also discuss the pros and cons of those two structures.
参见http://en.wikipedia.org/wiki/Adjacency_list和http://en.wikipedia.org/wiki/Adjacency_matrix。
文章还讨论了这两种结构的优缺点。
回答by G-Wiz
Depends on what other requirements you have. A naive, simple approach could be
取决于你有什么其他要求。一个天真的，简单的方法可能是
class Node
{
List<Node> edges;
int id;
}
where you'd have a List of all the nodes in the graph. The problem is this can become inconsistent; e.g. node A might be in node B's edges list, but node B might not be in node A's list. To get around this, you could model it as such:
您将拥有图中所有节点的列表。问题是这可能会变得不一致；例如，节点 A 可能在节点 B 的边列表中，但节点 B 可能不在节点 A 的列表中。为了解决这个问题，你可以这样建模：
class Edge
{
Node incidentA;
Node incidentB;
}
class Node
{
int id;
}
Again, you'd have List and List of all the edges and nodes in the system. Of course analyzing this data structure would be done in a very different way than in the other approach.
同样，您将拥有系统中所有边和节点的列表和列表。当然，分析这种数据结构的方式与其他方法截然不同。
回答by rai.skumar
Graph implementation depends on what you going to do with it. But for most cases Adjacency list based implementation helps.
图的实现取决于你打算用它做什么。但在大多数情况下，基于邻接列表的实现会有所帮助。
In Java you can do it using a Map<>. Here is generic Adjacency List based Graph.Javaimplementation on my blog.
在 Java 中，您可以使用 Map<> 来实现。这是我博客上基于Graph.Java 的通用邻接列表实现。
回答by Kuldeep Singh
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);
}
}
