Basic Graph Implementation in Java

Basic Graph Implementation in Java

Image for post

There are two fundamental ways we implement a graph in Java.

  1. By using an Adjacency Matrix
  2. 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:

Image for post

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.

1

No Responses

Write a response