| Great! you got the
adjacency matrix of a graph, but that does not mean you can surf through
that graph. Well, you got specific procedures to traverse a graph, viz.
Depth First Search and Breadth First Search.
We have seen traversal of a list, which
we did by sequentially printing the values in the list. In graphs,
traversal means visiting every vertex in the graph (and you might
process the value of that visited vertex). In sequential traversing of a list we
start from the first element and finally reach the last element by sequentially
incrementing the list's INDEX value by 1 every time.
Depth First
Search:-
Here, the starting point can be any vertex and the next
vertex to be visited is decided by the traversal you choose. If you
choose the DFS, the next vertex to be visited will be the adjacent
vertex (to the starting point), which has the highest depth
value(??????...look at the graph below) and then the next adjacent
vertex with the next higher depth value and so on till all the adjacent
nodes for that vertex are not visited. We repeat this same procedure for
every visited vertex of the graph.
Well, I got to explain this with the help
of a graph -
| If V1 is
the starting point of my traversal then, as you can see - V2, V3
and V8 are its adjacent vertices and so in the Adjacency List of
V1. Now, I am suppose to visit these vertices, but as this is DFS,
I should visit V8 first and then V2 and V3. So, to keep track of
which vertex to be visited next, we make use of a STACK, which
holds these vertex values in the DFS order. Let's see the
algorithm... |
 |
Algorithm:-
Step-1: Set the
starting point of traversal and push it inside the stack
Step-2: Pop the stack and add the popped vertex to the list of visited
vertices
Step-3: Find the adjacent vertices for the most recently visited vertex(
from the Adjacency Matrix)
Step-4: Push these adjacent vertices inside the stack (in the increasing
order of their depth) if they are not visited and not there in the stack
already
Step-5: Go to step-2 if the stack is not empty
C implementation:-
It's a pretty
lengthy one and so I would suggest you to download
it and study. The dfs.c file does not have enough comments but
you can always ask me for any clarifications. I have strictly followed
the algorithm for the implementation.
Breadth First Search:-
We make use of a
QUEUE here instead of a stack and the adjacent vertices are inserted
inside the queue in the increasing order of their BREADTH, so that the
first adjacent vertex to be visited will be the one with the least
breadth value. Try out implementation on your own after you study the
DFS one.
Note:-
We
push the adjacent vertices in the stack in the increasing order of their
depth values so that when you pop the stack, you visit the vertex with
higher depth value first and then the next higher depth value.
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
|
