Depth First Search MCQ Quiz in मराठी - Objective Question with Answer for Depth First Search - मोफत PDF डाउनलोड करा

The search starts at node Q → mark it as visited.

Q is connected to P, V, W, R, S and T.

If P is visited after Q immediately, possible sequences will be

QPVXWRTUS

QPSUTRWXV

If W is visited after Q immediately, possible sequences will be

QWRTUSPVX

QWXVPSUTR

If T is visited after Q immediately, possible sequences will be

QTUSPVXWR

QTRWXVPSU

Depth-first search explores edges out of the most recently discovered vertex u that still has unexplored edges leaving it. Once all of u’s edges have been explored, the search 'backtracks' to explore edges leaving the vertex from which u was discovered.

In DFS, LIFO principle used. Hence stack is best data structure for DFS traversal

In BFS, FIFO principle used. Hence queue is the best data structure for BFS traversal. 

The correct answer is More than one of the above.

Key Points

• Graph traversal algorithms are techniques used to visit all the nodes in a graph systematically.
  • Common graph traversal algorithms include Depth-First Search (DFS) and Breadth-First Search (BFS).
• Greedy, Divide and Conquer, and Dynamic Programming are not graph traversal algorithms.
  • Greedy algorithms make the optimal choice at each step to find the overall optimal way to solve the problem.
  • Divide and Conquer algorithms break the problem into smaller sub-problems, solve each sub-problem recursively, and combine their solutions to solve the original problem.
  • Dynamic Programming is used to solve problems by breaking them down into simpler sub-problems and storing the results of these sub-problems to avoid redundant work.

Additional Information

• Depth-First Search (DFS) and Breadth-First Search (BFS) are the primary graph traversal algorithms used in various applications, including pathfinding and topological sorting.
• While Greedy, Divide and Conquer, and Dynamic Programming are important algorithm design paradigms, they are not specifically used for graph traversal.
• Understanding the appropriate use cases for each algorithmic approach is crucial for solving complex computational problems efficiently.

The correct answer is option 4.

Explanation:

Depth First Search (DFS) is graph traversal algorithm uses stack data structure.

Option I : a b e g h f  : visit a; insert connected node of a, b;  insert connected node of b, e ;  insert connected node of e, g ;  insert connected node of g, h ; insert connected node of h, f .

Option II : a b f e h g : visit a; insert connected node of a, b; insert connected node of b, f ; Next to insert the connected node of f, which is either g or h; but e is not possible.

Option III : a b f h g e : visit a; insert connected node of a, b;  insert connected node of b, f ;  insert connected node of f, h ;  insert connected node of h, g ; insert connected node of g, e .

Option IV : a f g h b e: visit a; insert connected node of a, f;  insert connected node of f, g ;  insert connected node of g, h ;  insert connected node of h, b ; insert connected node of b, e .

The Correct answer is option 4.

Explanation:

 Depth first ordering :  Depth First Search (DFS) is graph traversing or searching algorithm using stack.

 Dominators : A node u is said to dominate another node v, wrt source node S, if all the paths from S to v in the graph must pass through node u.

Depth First Search and Breadth-First Search can be used to most efficiently find whether a cycle is present in a given graph

Complexity Analysis: (DFS)

Time Complexity: O(V+E).
Space Complexity: O(V).
To store the visited and recursion stack O(V) space is needed.

The correct answer is option 3:

‘Finding diameter of the graph’ and ‘Finding bipartite graph’ are the application of Breath First Search (BFS) on the graph.

Some other applications of BFS are:

• BFS is used to verify whether the given graph is Connected or not.
• We can find out the number of connected components in the given graph using BFS.
• BFS is used to verify whether the given graph contains Cycle or not.
• BFS is used to find out the single source shortest path in the given Un-weighted graph.

Breadth-first search is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

A queue is used to implement a breadth-first search.

Enque node G in the queue.

Queue: G

Mark it as visited. Dequeue G and enqueue its non-visited adjacent nodes.

Queue: A H I J

Mark A as visited. Dequeue A and enqueue its non-visited adjacent nodes.

Queue: H I J B

Mark H as visited. Dequeue H and enqueue its non-visited adjacent nodes.

Queue: I J B D E K

Mark I as visited. Dequeue I and enqueue its non-visited adjacent nodes.

Queue: J B D E K

Mark J as visited. Dequeue J and enqueue its non-visited adjacent nodes.

Queue: B D E K

Mark B as visited. Dequeue B and enqueue its non-visited adjacent nodes.

Queue: D E K​ C

Mark D as visited. Dequeue D and enqueue its non-visited adjacent nodes.

Queue: E K C

Mark E as visited. Dequeue E and enqueue its non-visited adjacent nodes.

Queue: K C

Mark K as visited. Dequeue K and enqueue its non-visited adjacent nodes.

Queue: C

Mark C as visited. Dequeue C and enqueue its non-visited adjacent nodes.

Queue: Empty queue

Hence traversal is GAHIJBDEKC is only possible

Therefore option 1, 2 and 4 are incorrect BFS traversal

Some of the sequences of the node in the order they are first visited:

ABCDEFG

ACEGFDB

ABDFGEC

ACBDEGF

ACBDFGE

ABCEGFD