Adjacency Matrix representation of graph in C++

An adjacency matrix is a square matrix used to represent a finite graph. It is a way of representing a graph as a matrix of booleans (0’s and 1’s). The boolean value of the matrix indicates if there is a direct path between two vertices.

Adjacency Matrix representation of graph

Graph can be represented as adjacency list as well as adjacency matrix. In adjacency matrix format, we use ‘0’ and ‘1’ for the representation of graph. Let a[n][j] be the adjacency matrix for a given undirected graph and if there will be path from node ‘x’ to node ‘y’  then in a[x][y] will become to 1 and a[y][x] will also become 1. Adjacency Matrix is always symmetric.

For example we have the graph given below

 1----2
 |    |
 |    |
 3----4----5

Adjacency Matrix representation of the above graph is given below

  1 2 3 4 5
1 0 1 1 0 0
2 1 0 0 1 0
3 1 0 0 1 0
4 0 1 1 0 1
5 0 0 0 1 0
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>v(n+1,vector<int>(n+1,0));
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x][y]=1;
        v[y][x]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *