BFS DFS

What is the shortest path from node A to node F?

• A -> B -> D -> F

• A -> C -> B -> E -> F

• A -> F

• A -> C -> E -> F

Traversal of a graph is different from tree because

• DFS of a graph uses stack, but inorrder traversal of a tree is recursive

• There can be a loop in graph so we must maintain a visited flag for every vertex

• BFS of a graph uses queue, but a time efficient BFS of a tree is recursive.

• All of the above

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

• MNOPQR

• NQMPOR

• QMNPRO

• QMNPOR

Consider the following graph,

Among the following sequences:

(I) a b e g h f

(II) a b f e h g

(III) a b f h g e

(IV) a f g h b e

Which are depth first traversals of the above graph?

• I, II and IV only

• I and IV only

• II, III and IV only

• I, III and IV only

The data structure used for Depth First Algorithm is

• STACK

• QUEUE

• BOTH STACK & QUEUE

• NONE OF THESE