|
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 -
|
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.
Related Operations:
Concept
-- non-directed, directed and weighted
Adjacency matrix of a Graph
Linked representation of a Graph
Traversals – Depth First & Breadth first Search
Transitive closure/ Warshall’s algorithm
Shortest Path Algorithm
Spanning Tree Algorithm
|
|
