Graph Representation

Introduction

There are many ways to represent a graph. The two most common ways of representing a graph are explained below:

Adjacency matrix

An adjacency matrix is a V*V binary matrix A. Element $A_{i,j}$, is 1 if there is an edge from vertex i to vertex j. Else, $A_{i,j}$, is 0.

Note: A binary matrix is a matrix in which the cells can have only one of two possible values - either 0 or 1.

The adjacency matrix can also be modified for the weighted graph in which instead of storing 0 or 1 in $A_{i,j}$ the weight or cost of the edge will be stored.

• In an undirected graph, if $A_{i,j}$ = 1, then $A_{j,i}$ = 1.
• In a directed graph, if $A_{i,j}$ = 1, then $A_{j,i}$ may or may not be 1.

The adjacency matrix provides constant-time access $(O(1))$ to determine if there is an edge between two nodes. The space complexity of the adjacency matrix is O($V^{2}$).