该图非常大,但是不带方向,边不带权重。
在我的实现中,我必须找到具有最大度数的顶点,并对顶点和边进行删除。
链表?ArrayList?Map?
哪一个更适合我的实现?
用于表示图形的两种基本数据结构是:
邻接表
邻接矩阵
请参考http://en.wikipedia.org/wiki/Adjacency_list和http://en.wikipedia.org/wiki/Adjacency_matrix了解这两种结构的优缺点。
我的建议是将顶点存储在优先队列中。这样,您就可以非常快速地访问具有最高度数的顶点。至于如何实现顶点,我会将每个相邻的顶点存储在某种集合数据结构中,例如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());
}
...
}
根据上述建议,答案应该是
使用LinkedList的Map...
你的数据结构可以像这样(根据你的要求而变化)...
Map<?, List<?>>
<Node-name, List-of-nodes-connected-to-it>
图的实现取决于你要做什么。但对于大多数情况,基于邻接列表的实现是有帮助的。
在Java中,你可以使用Map<>来实现它。这里是我博客上通用的基于邻接列表的Graph.Java实现。
如果您的算法需要查找最大度数,则需要一个按度数排序的数据结构,例如优先队列。
然后您需要存储图本身。为了快速删除,我建议使用类似于稀疏数组结构的东西。如果您必须使用java.util数据结构,则从顶点到连接顶点列表的HashMap提供O(1)删除。
如果您可以使用第三方库,则有这里的答案列表,其中JGraph和JUNG似乎最受欢迎。
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);
}
}
这取决于您还有什么其他要求。一个天真、简单的方法可能是
class Node
{
List<Node> edges;
int id;
}
在图中,您可能会有所有节点的列表。问题是这可能会变得不一致;例如,节点A可能在节点B的边缘列表中,但节点B可能不在节点A的列表中。为了解决这个问题,您可以将其建模如下:
class Edge
{
Node incidentA;
Node incidentB;
}
class Node
{
int id;
}
同样,您将拥有系统中所有边缘和节点的列表和列表。当然,分析这个数据结构的方式与其他方法完全不同。