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.


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.

using namespace std;

class G
    int vertices;
    bool **matrix;
    G (int vertices);
    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;
     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 */
return 0;

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

Related Contents to follow