Graph Traversal
Graph traversal is a technique used for searching a vertex in a
graph. The graph traversal is also used to decide the order of
vertices is visited in the search process. A graph traversal finds
the edges to be used in the search process without creating
loops. That means using graph traversal we visit all the vertices of
the graph without getting into looping path.
There are two graph traversal techniques and they are as
follows...
1. DFS (Depth First Search)
2. BFS (Breadth First Search)
DFS (Depth First Search):
DFS traversal of a graph produces a spanning tree as final
result. Spanning Tree is a graph without loops. We use Stack
data structure with maximum size of total number of vertices in
the graph to implement DFS traversal.
We use the following steps to implement DFS traversal...
Step 1 - Define a Stack of size total number of vertices in the
graph.
Step 2 - Select any vertex as starting point for traversal.
Visit that vertex and push it on to the Stack.
Step 3 - Visit any one of the non-visited adjacent vertices of
a vertex which is at the top of stack and push it on to the
stack.
Step 4 - Repeat step 3 until there is no new vertex to be
visited from the vertex which is at the top of the stack.
Step 5 - When there is no new vertex to visit then use back
tracking and pop one vertex from the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final
spanning tree by removing unused edges from the graph
Back tracking is coming back to the vertex from which we reached the current vertex.
Example:
Example 2:
Applications of DFS:
Following are the problems that use DFS as a building block.
1) For an unweighted graph, DFS traversal of the graph produces
the minimum spanning tree and all pair shortest path tree. DFS is
at the heart of Prims and Kruskals algorithms.
2) Detecting cycle in a graph
A graph has cycle if and only if we see a back edge during DFS.
So we can run DFS for the graph and check for back edges.
3) Path Finding
DFS algorithm can be used to find a path between two given
vertices u and z.
i) Call DFS(G, u) with u as the start vertex.
ii) Use a stack S to keep track of the path between the start vertex
and the current vertex.
iii) As soon as destination vertex z is encountered, return the path
as the
contents of the stack
4) Topological Sorting
DFS is an intermediate step for topological sorting.
5) Finding Strongly Connected Components of a graph A directed
graph is called strongly connected if there is a path from each
vertex in the graph to every other vertex. (See this for DFS based
algo for finding Strongly Connected Components)
6) DFS is very helpful in solving almost all the maze puzzles.
Most of the maze puzzles can be converted into Graph problems
and traversals result into the solution. DFS can be adapted to find
all solutions to a maze by only including nodes on the current path
in the visited set.
