Subjects
Advanced Java  2160707
Compiler Design  2170701
Data Mining And Business Intelligence  2170715
Data Structure  2130702
Database Management Systems  2130703
Information And Network Security  2170709
Mobile Computing And Wireless Communication  2170710
Operating System  2140702
Software Engineering  2160701
Theory Of Computation  2160704
Semester
Semester  1
Semester  2
Semester  3
Semester  4
Semester  5
Semester  6
Semester  7
Semester  8
Data Structure
(2130702)
DS2130702
Summer2014
Question4a
BE  Semester
3
Summer2014

06/04/2014
Goto Question Paper
Q4) (a)
Explain DFS and BFS with example
7 Marks
Most graph problems involve traversal of a graph. Traversal of a graph means visit each node exactly once.
Two commonly used graphs traversal techniques are
Depth First Search (DFS)
Breadth First Search (BFS)
Depth First Search (DFS)
It is like preorder traversal of tree.
Traversal can start from any vertex vi.
Vi is visited and then all vertices adjacent to vi are traversed recursively using DFS.
Since graph can have cycles, we must avoid revisiting a node. To do this when we visit a vertex V, we marks it visited as visited should not be selected for traversal.
Breadth First Search (BFS)
This methods starts from vertex V
_{0}
.
V0 is marked as visited. All vertices adjacent to V
_{0}
are visited next.
Let vertices adjacent to V
_{0}
are V
_{1}
, V
_{2}
, V
_{3}
, V
_{4}
.
V
_{1}
, V
_{2}
, V
_{3}
and V
_{4}
are marked visited.
All unvisited vertices adjacent to V
_{1}
, V
_{2}
, V
_{3}
, V
_{4}
are visited next.
The method continuous until all vertices are visited.
The algorithm for BFS has to maintain a list of vertices which have been visited but not explored for adjacent vertices. The vertices which have been visited but not explored for adjacent vertices can be stored in queue.
Initially the queue contains the starting vertex.
In every iteration, a vertex is removed from the queue and its adjacent vertices which are not visited as yet are added to the queue.
The algorithm terminates when the queue becomes empty.