Graph data structure tutorial 2. Graph Representation Adjacency Matrix

In this chapter we shall learn about:

2.1 Introduction
2.2 Understanding of Graph Representation adjacency matrix with an example
2.3 Implementation
2.4 Output

2.1 Introduction:

In this tutorial we shall see how to store a graph with the help of a matrix.

As it stores the path between 2 vertices, it is called as adjacency matrix.
The idea is to take 2D array of size V * V, then mark the index as “1” if there exist an edge between those 2 vertices.

2.2 Understanding of Graph Representation adjacency matrix with an example

Example 1: consider an undirected graph as shown below:

Our adjacency matrix will look like below:

Now we shall choose the edge “A”, we fill “1” for all the nodes it is connected. As the graph is undirected, if there is a path from A->B, then there is a path between B->A. So adjacency matrix for vertex “A” is as shown below:

So the final matrix will be as shown below:

Time taken to find all the nodes that are adjacent to the given node?

If we want to know the adjacent node for the vertex “A”, then we just search the “A” index and check if the value is 0 or 1.

Hence the time taken will be O(V)

Example 2: Consider a Directed graph as shown below:

Here to represent the adjacency, we give the weight of the edge. And if there are no connection, then we give a very large value like infinity.

The adjacency matrix for a weighted graph is as shown below

Here memory consumption is O(V^2). For a very large value of V, the memory consumption will be very high.
Hence we need to find a more efficient way to represent a graph. We can do it with the help of Adjacency List.

2.3 Implementation of Graph Representation using Adjacency Matrix using C++

#include <iostream>

using namespace std;

int main()
{
    int V = 5; // we create a 5x5 matrix
    int i;
    int j;
    int choice;
    
    // 2D array to store the values
    int adj[V][V];

    // initialize the matrix to 0
    for (i = 0; i < V; ++i)
        for (j = 0; j < V; ++j)
           adj[i][j] = 0;
    

    // now, as there is a path from node to same node,
    // make it reachable
    for (i = 0; i < V; ++i)
        adj[i][i] = 1;

    //input the value
    while (1)
    {
        cout<<"Input the value for i and j"<<endl;
        cin >> i >> j;
        adj[i][j] = 1;
        adj[j][i] = 1;
        cout<<"Path created from "<<i << " to "<<j<<endl;
        
        cout<<"Enter 1 to continue, 0 to qut"<<endl;
        cin>>choice;
        if(choice == 0)
            break;

    }
    
    cout << "Adjacency Matrix is " << "\n";
    for (i = 0; i < V; ++i)
    {
        for (j = 0; j < V; ++j)
        {
            cout << adj[i][j] << " ";
        }
        cout << "\n";
    }       
    return 0;
}

2.4 Output:

Input the value for i and j

1

2

Path created from 1 to 2

Enter 1 to continue, 0 to quit

1

Input the value for i and j

3

4

Path created from 3 to 4

Enter 1 to continue, 0 to quit

0

Adjacency Matrix is

1 0 0 0 0

0 1 1 0 0

0 1 1 0 0

0 0 0 1 1

0 0 0 1 1