Draw a graph and illustrate how depth-first search and breadth-first search differ

• Tweet
• Email

• Tweet
• Email

This was the first question in Computer Officer Examination in 2010 conducted by Public Service Commission (Lok Sewa Aayog). This question is from the section ‘Data Structures and Algorithms’. The question carries 10 marks.

Answer

Breadth-first search (BFS) and depth-first search (DFS) are the two algorithms used for traversing and searching a node in a graph. They can also be used to find out whether a node is reachable from given node or not.

In depth-first search traversal  we try to go far from the root node.  Nodes are visited by going through the depth of the tree from starting node. When we reach at the node which does not have any children then we backtrack and visit the child nodes on another branch.

The depth-first search traversal of above graph will be:

A  B  E  F  C  D

In case of breadth-first search traversal, the aim is to traverse the graph as close as possible to the root node. Breadth-first search visits the nodes level by level, it will start with level 0 which is the root node, and then move to the next level and so on.

The breadth-first search traversal of above graph will be:

A  B  C  D  E  F

Stacks are used to implement the depth-first search and in case of breadth-first search queue is used.

Note: You are welcome to suggest more differences and or explanation to this answer.

Tagged As: BFS, Breadth-First Search, computer officer exam, Data Structures and Algorithms, Depth-First Search, DFS, Graphs, Lok Sewa Aayog, Public Service Commission, Solved Question of Computer Officer