Data Structures: Graph - Adjacency Matrix

As I have explained basic concepts of the Graph in my previous post, I hope it is clear to you people. Now, I am going to show, how you can represent this graph in programming. 

Now, if I call these vertices as to be the pieces of similar information and the edges as to be the various linkages between them, then, you can certainly think of representing any Graph with the help of Linked Lists, can't you?
Well, we'll see that implementation in our next section. But for now, you've a bit simpler representation of Graphs, the Adjacency Matrix. This matrix shows you all the direct linkages between the vertices; meaning the direct edges between the vertices. Let me explain this with the help of an example -

Consider, this directed graph. It has five vertices and five edges - AD, BD, CB, DE and EC. The Adjacency matrix for this will be -

	A	B	C	D	E
A	0	0	0	1	0
B	0	0	0	1	0
C	0	1	0	0	0	1 if the edge is there 0 if no edge is there
D	0	0	0	0	1
E	0	1	0	0	0

Now you know why it is called as an adjacency matrix. It only shows the direct paths between the vertices but you can see there exist paths which have intermediate vertices also; like from A to B you have D->E->C. 

Remember, it does not matter if the graph is weighted, the adjacency matrix is gonna remain the same.

Note:- When I say route, I mean the direct path between the vertices and that no other vertex is there in that path except the two adjacent vertices forming the edge. I guess you know how to store a 2D-matrix in an array! That is left for your practice.

#include <iostream>

#define MAX 5

using namespace std;


int main()

{

int E, V[MAX]; //E=number of Edges, V=Vertices

int i, j;

int temp1=0, temp2=0;

int adj_mat[MAX][MAX] = {0}; //Adjacency Matrix

cout<<"Enter Vertices"<<endl; //Enter all the vertices. for example 1,2,3,4 etc..

for(i=0; i<MAX; i++)

{

cin>>V[i];

}

cout<<"Enter number of Edges"<<endl;

cin>>E; //Total number of edges between vertices.



for(j=0; j<E; j++)

{

cout<<"Edge #"<<j+1<<" "; //j+1 because we will be starting from Edge #1 and not 0.

cin>>temp1; //Path from

cin>>temp2; //Path To

//Path from and to, are in case of directed graph.

adj_mat[temp1-1][temp2-1] = 1; //Placing 1 in appropriate place in adjacency matrix

}
for(i=0; i<MAX; i++)

{

for(j=0; j<MAX; j++)

{

cout<<adj_mat[i][j]<<" "; //Display the adjacency matrix.

}

cout<<endl;

}

return 0; //Get back in where you came from... :)

}