Graph Representation: Adjacency Matrix and Adjacency List

Reading time: 20 minutes | Coding time: 5 minutes

Pseudocode

The pseudocode for constructing Adjacency Matrix is as follows:

1. Create a matrix A of size NxN and initialise it with zero.
2. Iterate over each given edge of the form (u,v) and assign 1 to A[u][v]. Also, If graph is undirected then assign 1 to A[v][u]. 

Implementation

   /*
      This code is for constructing adjacency matrix for undirected graph, with minor change it will also work for directed graph.
   */
   #include <bits/stdc++.h>
   using namespace std;
   int main()
   {
       // where n is number of vertices and m is number of edges
   int n, u, v, m;
   cin>> n>> m;
   int A[n][n];
   for(int i=0; i&lt;n; i++)
   {
        for(int j=0; i&lt;n; j++)
            A[i][j]=0;
   } 
   for(int i=0; i&lt; m; i++)
   {
       cin>> u>> v;
       A[u][v]=1;
       A[v][u]=1; // In case of directed graph this statement is removed. 
   }
   // After above loop Adjcency matrix is ready.
    for(int i=0; i&lt;n; i++)
   {
        for(int j=0; j&lt;n; j++)
            cout&lt;&lt;A[i][j]&lt;&lt;" ";
        cout &lt;&lt; "\n";
   } 
   return 0;
 }

Pseudocode
The pseudocode for constructing Adjacency Matrix is as follows:

1. Create an array A of size N and type of array must be list of vertices. Intially each list is empty so each array element is initialise with empty list.
2. Iterate each given edge of the form (u,v) and append v to the uth list of array A. Also, If graph is undirected append u to the vth list of array A.

Implementation

   /*
      This code is for constructing adjacency list for undirected graph, with minor change it will also work for directed graph.
   */
   #include <bits/stdc++.h>
   using namespace std;
   int main()
   {
       // where n is number of vertices and m is number of edges
       int n, u, v, m;
       cin>> n>> m;
       vector< vector<int> > A(n);
       for(int i=0; i< m; i++)
       {
           cin>> u>> v;
           A[u].push_back(v);
           A[v].push_back(u); // In case of directed graph this statement is removed. 
       }
       // After above loop Adjcency List is ready.
        for(int i=0; i<n; i++)
       {
            cout<< i<< " ----> ";
            for(int j=0; j<A[i].size(); j++)
                cout<< A[i][j]<< " -->";
            cout <<  "\n";
       } 
       return 0;
     }
 

Complexity

N denotes the number of nodes/ vertices and M denotes the number of edges

degree(V) denotes the number of edges from node V

Adjacency Matrix Complexity

Space: O(N * N)

Check if there is an edge between nodes U and V: O(1)

Find all edges from a node: O(N)

Adjacency List Complexity

Space: O(N + M)

Check if there is an edge between nodes U and V: O(degree(V))

Find all edges from a node V: O(degree(V))

Where to use?

As we have seen in complexity comparisions both representation have their pros and cons and implementation of both representation is simple. It is recommended that we should use Adjacency Matrix for representing Dense Graphs and Adjacency List for representing Sparse Graphs.

Note: Dense Graph are those which has large number of edges and sparse graphs are those which has small number of edges.

Application

1. Adjacency Matrix: Adjacency matrix is used where information about each and every possible edge is required for the proper working of an algorithm like :- Floyd-Warshall Algorithm where shortest path from each vertex to each every other vertex is calculated (if it exists). It can also be used in DFS (Depth First Search) and BFS (Breadth First Search) but list is more efficient there. Sometimes it is also used in network flows.
   

2. Adjacency List: Adjacency List is a space efficient method for graph representation and can replace adjacency matrix almost everywhere if algorithm doesn't require it explicitly. It is used in places like: BFS, DFS, Dijkstra's Algorithm etc.