# GRAPH and its representation:TUTORIAL

*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 | 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; } }

## Leave a Reply