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.