There are two fundamental ways we implement a graph in Java.
- By using an Adjacency Matrix
- By using an Adjacency List
So which should you use? It depends?on what operations you want to perform on the graph.
Adjacency Matrix
Pros:
- Fast lookup for finding an edge ? O(1) time
- Better for dense graphs i.e., having a lot of edges
Cons:
- Uses O(V) space
- Iterates over all of the edges in O(V) time
V = number of vertices
Adjacency List
Pros:
- Uses O(V+E) space (worst case)
- Better for sparse graphs i.e., having less number of edges
Cons:
- Look up for finding an edge takes O(V) time
V = number of vertices, E = number of edges
Most graphs are pretty sparse and typically V >> E so adjacency lists are widely used.
Here?s an implementation of a Graph using Adjacency List in Java
I implemented a weighted directed graph as a HashSet of vertices. We can implement an undirected and/or unweighted graph using the same approach (refer to the comments in the code).
Each vertex has a name and contains a list of all of its outgoing edges.(I used an ArrayList. You could use a LinkedList too.)
Each edge has a weight and a destination vertex.
Our Input graph looks like this:
Output:
vertex name: 3: destVertex: 2 weight: 4 | vertex name: 0: destVertex: 1 weight: 2 | vertex name: 1: destVertex: 2 weight: 3 | vertex name: 2: destVertex: 0 weight: 1 | destVertex: 3 weight: 1 |
Thanks for reading. Give this post a clap if you find it interesting. Have any doubts? Please feel free to leave it in the comments below. Namaste!
Originally published at mithratalluri.wordpress.com on October 13, 2018.
