Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java - Which is the best implementation structure for Graph?

Tags:

java

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?

like image 450
user236691 Avatar asked Dec 22 '09 09:12

user236691


People also ask

What is the best way to implement a graph in Java?

Usually, we implement graphs in Java using HashMap collection. HashMap elements are in the form of key-value pairs. We can represent the graph adjacency list in a HashMap. A most common way to create a graph is by using one of the representations of graphs like adjacency matrix or adjacency list.

What are the two approaches to graph implementation?

There are two traditional approaches to representing graphs: The adjacency matrix and the adjacency list.


2 Answers

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.

like image 75
Chris Avatar answered Sep 28 '22 04:09

Chris


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.

like image 24
svenningsson Avatar answered Sep 28 '22 04:09

svenningsson