There are two ways of representing graph, one as a Matrix and another one as list. Matrix representation is called Adjacency Matrix and list representation is called Adjacency List.

Adjacency Matrix Representation

This is a matrix representation of a graph where size of matrix will be numbers of vertices. If there are N number of vertices then adjacency matrix would be of size M[NxN].  If there exists an edge between ith vertex and jth vertex then M[i][j]=1 otherwise M[i][j]=0.

Let us represent below undirected graph as adjacency matrix.

 udg

A B C D
A 0 1 1 1
B 1 0 1 1
C 1 1 0 1
D 1 1 1 0

 

Now implement this in c++

G = { V,E} , where E = { (A,B), (A,C),(A,D),(B,A),(B,C),(B,D),(C,A),(C,B),(C,D),(D,A),(D,B),(D,C) }

In the above figure V=4 ( number of vertices ) , G represents the graph and E is set of edges { (A,B), (A,C),(A,D),(B,A),(B,C),(B,D),(C,A),(C,B),(C,D),(D,A),(D,B),(D,C) }

So, our matrix will be of size 4×4, we have to fill the ith row and jth column with 0 and 1 where 1 represents an edge.

#include<iostream>
#include<unistd.h>
using namespace std;

class G
{
    int vertices;
    bool **matrix;
    public:
    G (int vertices);
   ~G();
    void AddEdge (int a,int b);
    void printMatrix();
};

G::G(int vertices)
{
     this->vertices = vertices;
     matrix = new bool *[vertices];
     for( int i=0; i< vertices ;i++)
     {
          matrix[i] =new bool [vertices];
          for(int j=0;j<vertices;j++)
          {
             matrix[i][j] = 0;
          }
      }
}
G::~G()
{
     for( int i =0; i< vertices; i++)
     delete[] matrix[i];
delete []matrix;
}

void G::AddEdge(int a,int b)
{
    matrix[a][b] = 1;
}
int main ()
{
    G *graph = new G(4);
    graph->AddEdge(0,1);//  (A,B)
    graph->AddEdge(0,2); // (A,C)
    graph->AddEdge(0,3); //(A,D)
    graph->AddEdge(1,0); //(B,A)
    graph->AddEdge(1,2); //(B,C)
    graph->AddEdge(1,3); //(B,D)
    graph->AddEdge(2,0); //(C,A)
    graph->AddEdge(2,1); //(C,B)
    graph->AddEdge(2,3); //(C,D)
    graph->AddEdge(3,0); //(D,A)
    graph->AddEdge(3,1); //(D,B)
    graph->AddEdge(3,2); //(D,C)
   /* print adjacency matrix now */
   graph->printMatrix();
return 0;
}

void G::printMatrix()
{
for(int i=0;i< vertices; i++){
      for(int j=0;j< vertices; j++){
      cout<< matrix[i][j]<<" " ;
      }
      cout<<endl;
}
}



Related Contents to follow