Graph Data Structure in Java, easy in 5 minutes

The post introduces Graph Data Structure in Java, both concept and implementation. A graph data structure is a collection of nodes that are connected to other nodes. Every connection is an edge from one node to another. Let’s dig deeper.

Graph Data Structure in Java

Graph example

Now, you can try to discovery a bit about how Facebook uses graph data structure. On facebook, everything is a node. That might include User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note…anything that has data is a node. When you post a story, join group, like page etc., an edge is created for that connection. So Facebook uses graph data structure to store its data (nodes and edges).

In short, a Graph is a data structure that consists of:

  • A collection of vertices V (also called nodes)
  • A collection of edges E, which connect a pair of vertices.

Graph Data Structure in Java

The above graph may be described like this:

Graph Terminology
  • Adjacency: A vertex is said to be adjacent to another vertex if there is an edge connecting them. In the above graph, vertex 20 and 30 are adjacent because there is an edge between them. But vertex 20 and 40 are not adjacent as there is no edge between them.
  • Path: A path is simply a collection of edges that allows you to go from a vertex to another vertex. In the above graph, paths of vertex 10 and vertex 40 are 10-20, 20-30, 30-40 and 10-40 .
  • Directed Graph: A graph in which edges feature a direction so such a graph is known as a directed graph. The direction is represented by arrows to show the direction of the edge.

directed graph data structure

Graph Representation

A graph can be represented commonly in adjacency matrix and adjacency list. Each one has their pros and cons in a different set-up.
1. Adjacency Matrix
An adjacency matrix is 2D array of V x V vertices, with dimensions equivalent to the number of vertices in the graph. Each row and column represent a vertex. The elements of the adjacency matrix have values 0 or 1. A value 1 indicates an adjacency between the vertices and a value of 0 otherwise. The above graph can be represented in an adjacency matrix below

Adjacency Matrix

Let’s have a look on this adjacency matrix, you see 10 and 20 is adjacency but 10 and 30 otherwise. This representation is easier to implement and efficient to query as well. However, it requires more space because we must reserve space for every possible link between all vertices(V x V).
2. Adjacency List
In general, an adjacency list represents a graph as an array of linked list. Each specified index of the array represents a vertex and each element in its linked list represents the other vertices that have an edge with that vertex. The above graph might be represented in an adjacency list like below

Adjacency List

This representation is comparatively difficult to implement and less efficient to query. But it is better space efficiency because it only stores the values for the edges.

Graph Operations

The most common graph operations are:

  • Graph Traversal
  • Check if element is present in graph
  • Add elements(vertex, edges) to graph
  • Finding path from one vertex to another vertex
Implement a Graph data structure in Java

I noticed that Java doesn’t have a default implementation of the graph data structure. But, you can implement a Graph Data Structure in Java using java collection to store its edges.

Here is the output of the above program

That’s all about Graph Data Structure in Java. You might refer to the other data structures in Java

References

Graph documentation

Please share it if you found this useful
Hide Buttons