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.




Related Contents to follow