Data Structure (2130702)

BE | Semester 3
  Summer-2014 | 06/04/2014

Q4) (a)Explain DFS and BFS with example

  • 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
    1. Depth First Search (DFS)
    2. 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 re-visiting a node. To do this when we visit a vertex V, we marks it visited as visited should not be selected for traversal.
Depth First Search (DFS) example

Breadth First Search (BFS)

  • This methods starts from vertex V0.
  • V0 is marked as visited. All vertices adjacent to V0 are visited next.
  • Let vertices adjacent to V0 are V1, V2, V3, V4.
  • V1, V2, V3 and V4 are marked visited.
  • All unvisited vertices adjacent to V1, V2, V3, V4 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.
Breadth First Search (BFS) example