Graph->Adjacency Matrix

1 if the edge is there
0 if no edge is there

Free Web Hosting Provider - Web Hosting - E-commerce - High Speed Internet - Free Web Page

Graphs->Adjacency Matrix

I said while describing the concepts of Graphs that its a collection of vertices and edges. 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 -

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.

Index || Doubts / Clarifications || Related Topics || Web Links