best data structure to represent a graph in JAVA?

general
,
1

Hi, i want to implement graphs to find out the longest distance present in a graph. What is the best way to implement it in JAVA?

1 Like
2

It’s very common to use adjacency list, so something like

List<Integer>[]

where array size is number of vertexes and you for vertex i you add all neighbors to the list…

1 Like
3

depends on what you want to achieve

4

There was an contest in Hackerrank.
https://www.hackerrank.com/contests/101sep13/challenges/jack-goes-to-rapture
It is a graph theory problem, with a lot of Nodes and Vertices.

As far as I know there are 2 main representations for graphs. 

1. AdjacencyList 
2. Matrix
     
I find the matrix way easier to interpret and debug. I feel it is also highly intuitive.

I use a laptop (2 GB Ram + Java / C++) for programming contests. I have found if there are 10000 nodes. Then (mostly) you wont be able to allocate the matrix. This is a short coming for matrix representations.
If you have a dense graph which is directed then 2-D matrix is a good option. This is very common in topcoder questions where the number of nodes is approximately 50. 
For Adjacency List there willinherently be some house keeping information. Eg. List size, next element pointers etc. Where as a matrix is just 2-D array of primitives


Adjacency list will use lesser space if the graph is less dense. This came in handy in the hacker rank problem I have mentioned. Although it is a shortest path problem please go through some of the submissions. The pundits haven't used adjacency lists either. They have used priority ques with Dijikstra's Algo.

Another interesting problem is the codejam pogo stick for the large data case. 
https://code.google.com/codejam/contest/2437488/dashboard#s=p1
This just implies if you have a >10000 nodes in the graph, You should find an optimization.
    
Another gotcha! If the number of nodes is less than 20 , Eg 16. You can just run a loop and test for optimal solution.
Eg . 3 Nodes  Run loop from 0 -> 7 
000
001 (Check if selection of last node will be optimal)
010 (Check if selection of middle node will be optimal)
011 (Check if selection of last 2 nodes will be optimal)
..


Conclusion 
Nodes <= 20 -> Just Iterate Brute Force
Nodes <= 50 -> Matrix 
Nodes >= 10000 -> Adj List or Ques :)