Java - Which is the best implementation structure for Graph?

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?

The two fundamental data structures for representing graphs are the

• adjacency list

• the adjacency matrix

see http://en.wikipedia.org/wiki/Adjacency_list and http://en.wikipedia.org/wiki/Adjacency_matrix.
The articles also discuss the pros and cons of those two structures.

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.

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.

From the above suggested the answer would be

Map with 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..

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.

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 HashMap from vertexes to the list of connected vertexes offers O(1) deletion.

If you could use 3rd party libraries, then there are a list of answers here of which JGraph and JUNG seem most popular.

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.Java implementation on my blog.

You could also have a look at specifically-designed libraries, like JUNG

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:

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.

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

    }

}