Graph Representations: A Comprehensive Guide

In this post, we will look at various graph representations and how to translate the representation to the code in Java.

Graph Representation

In order to represent a graph in code, you have to store information about

1. The Vertices which are part of the given Graph and,
2. The Edges which connect vertices

Graphs can be represented in various ways in programming. The most common representations are: Adjacency Matrix, Adjacency List and Edge List

Adjacency Matrix Representation of Graphs

An adjacency matrix is a 2D array used to represent a graph. In this representation, the graph is described by a square matrix A of size V x V where V is the number of vertices. Each element A[i][j] indicates whether there is an edge from vertex i to vertex j.

Characteristics

• Storage: Uses O(V2) space, where V is the number of vertices.
• Edge Presence: A[i][j] = 1 if there is an edge from vertex i to vertex j, otherwise A[i][j] = 0.
• Weighted Graphs: For weighted graphs, A[i][j] can store the weight of the edge.
• Use Case: Efficient for dense graphs where the number of edges E is close to V2, and for quickly checking the presence of edges.

Example