Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Graph Representations
Table of Contents

1 Adjacency Matrix

Adjacency matrix for Undirected Graph

Adjacency matrix for directed graphs

Adjacency List

Representing directed graphs using adjacency list

Graphs can be represented in multiple ways depending on the use case. The two most common methods are:

  • Adjacency Matrix
  • Adjacency List

Let’s break down both approaches with examples for undirected and directed graphs.

1 Adjacency Matrix

An adjacency matrix is a 2D array (or matrix) used to represent the presence or absence of edges between vertices.

  • The matrix is of size N × N, where N is the number of vertices.
  • Each cell (i, j) indicates whether there’s an edge from vertex i to vertex j.

Adjacency matrix for Undirected Graph

  • If an edge exists between vertex i and j, then both A[i][j] and A[j][i] are set to 1.
  • If no edge exists, both entries are 0.
  • The matrix is symmetric across the diagonal.

Example

Undirected Graph with 4 Edges (A-B, B-C, C-D, D-A)
Undirected Graph with 4 Edges (A-B, B-C, C-D, D-A)
Adjacency Matrix for the Above Graph with 4 Edges (A-B, B-C, C-D, D-A)
Adjacency Matrix for the Above Graph with 4 Edges (A-B, B-C, C-D, D-A)

Adjacency matrix for directed graphs

In a directed graph with N vertices, the adjacency matrix A will also be an N x N matrix. For a directed edge from vertex i to vertex j, the corresponding entry in the matrix (A[i][j]) will have the value of 1, indicating the presence of an edge from i to j. If there is no edge from vertex i to vertex j, the matrix entry will have the value of 0.

Example of a directed graph with 4 vertices (A, B, C, D) and 5 directed edges (A->B, A->C, C->D, D->B, D->C):

Directed Graph with 5 Edges (A->B, A->C, C->D, D->B, D->C)
Directed Graph with 5 Edges (A->B, A->C, C->D, D->B, D->C)
Image

The above figure explains the adjacency matrix of the directed graph in such a way that there is an edge between vertices A-C and A-B so 1 is placed there.

Adjacency List

An adjacency list stores each vertex alongside a list of its neighbors. It is space-efficient for sparse graphs (graphs with fewer edges).

  • Each node maps to a list of connected nodes.
  • It is commonly implemented using arrays or hash maps with linked lists or dynamic arrays.

Representing undirected graph using adjacency list

In an undirected graph, the edges between vertices have no direction. If vertex A is connected to vertex B, then vertex B is also connected to vertex A. As a result, the adjacency list for an undirected graph is symmetric. Here is an example of a undirected graph with four vertices (A, B, C, D) and four edges.

Image

Here is the adjacency list for the above-undirected graph. From vertex A there is an edge to vertex B and C in the graph. So in the adjacency list, there are two nodes from node A.

Image

Representing directed graphs using adjacency list

In a directed graph, the edges between vertices have a direction. If vertex X is connected to vertex Y, it does not necessarily mean that vertex Y is connected to vertex X. As a result, the adjacency list for a directed graph is not symmetric.

Example of a directed graph with 4 vertices (A, B, C, D) and 4 directed edges (A->B, A->C, C->D, D->B):

Image

Here is the adjacency list for the above directed graph. From vertex A there is an edge to vertex B and C in the graph. So in the adjacency list, there are two nodes from node A. From vertex B there is no edge coming out so the adjacency list contains no further node from node B.

Image
Mark as Completed

Table of Contents

1 Adjacency Matrix

Adjacency matrix for Undirected Graph

Adjacency matrix for directed graphs

Adjacency List

Representing directed graphs using adjacency list