CUET PG 2025 Computer PYQ — Consider the task of finding the shortest path in an unweighted g… | Mathem Solvex | Mathem Solvex
Tip:A–D to answerE for explanationV for videoS to reveal answer
CUET PG 2025 — Computer PYQ
CUET PG | Computer | 2025
Consider the task of finding the shortest path in an unweighted graph by using BFS and DFS.
Which of the following statements are true?
(A) BFS always finds the shortest path.
(B) DFS always finds the shortest path.
(C) DFS does not guarantee finding the shortest path.
(D) BFS does not guarantee finding the shortest path.
Choose the correct answer from the options given below:
Choose the correct answer:
A.
(B) and (D) only
B.
(A) and (C) only
(Correct Answer)
C.
(A) and (B) only
D.
(C) and (D) only
Correct Answer:
(A) and (C) only
Explanation
The correct answer is (A) and (C) only
BFS DFS Shortest Path in Unweighted Graphs Explained
This question asks us to determine which statements are true regarding the ability of Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms to find the shortest path in an unweighted graph.
Understanding BFS and Shortest Paths
Breadth-First Search (BFS) operates by exploring the graph layer by layer. It starts from a source node and visits all its direct neighbors. Then, it visits the neighbors of those neighbors, and so on. In an unweighted graph, where each edge has a cost of 1, BFS guarantees finding the shortest path. This is because BFS discovers nodes in increasing order of their distance (number of edges) from the source node. The first time BFS encounters any node, it has done so via the minimum number of edges possible, thus identifying the shortest path.
Statement (A): BFS always finds the shortest path. This statement is True for unweighted graphs.
Statement (D): BFS does not guarantee finding the shortest path. This statement is False.
Understanding DFS and Shortest Paths
Depth-First Search (DFS) explores as far as possible along each branch before it backtracks. It proceeds by going deeper into the graph along a path. Unlike BFS, DFS does not systematically explore nodes based on their distance from the source. It might traverse a long path to a node before exploring shorter paths. Consequently, DFS does not guarantee that it will find the shortest path in an unweighted graph.
Statement (B): DFS always finds the shortest path. This statement is False.
Statement (C): DFS does not guarantee finding the shortest path. This statement is True.
Summary of Statements
Based on the analysis:
Statement (A) is True.
Statement (B) is False.
Statement (C) is True.
Statement (D) is False.
The true statements are (A) and (C).
Selecting the Correct Option
We need to identify the option that lists only the true statements, which are (A) and (C). Let's examine the given choices:
Option Number
Statements
1
(B) and (D) only
2
(A) and (C) only
3
(A) and (B) only
4
(C) and (D) only
Option 2 correctly includes statements (A) and (C), which we have determined to be true. Therefore, Option 2 is the correct choice.
Explanation
The correct answer is (A) and (C) only
BFS DFS Shortest Path in Unweighted Graphs Explained
This question asks us to determine which statements are true regarding the ability of Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms to find the shortest path in an unweighted graph.
Understanding BFS and Shortest Paths
Breadth-First Search (BFS) operates by exploring the graph layer by layer. It starts from a source node and visits all its direct neighbors. Then, it visits the neighbors of those neighbors, and so on. In an unweighted graph, where each edge has a cost of 1, BFS guarantees finding the shortest path. This is because BFS discovers nodes in increasing order of their distance (number of edges) from the source node. The first time BFS encounters any node, it has done so via the minimum number of edges possible, thus identifying the shortest path.
Statement (A): BFS always finds the shortest path. This statement is True for unweighted graphs.
Statement (D): BFS does not guarantee finding the shortest path. This statement is False.
Understanding DFS and Shortest Paths
Depth-First Search (DFS) explores as far as possible along each branch before it backtracks. It proceeds by going deeper into the graph along a path. Unlike BFS, DFS does not systematically explore nodes based on their distance from the source. It might traverse a long path to a node before exploring shorter paths. Consequently, DFS does not guarantee that it will find the shortest path in an unweighted graph.
Statement (B): DFS always finds the shortest path. This statement is False.
Statement (C): DFS does not guarantee finding the shortest path. This statement is True.
Summary of Statements
Based on the analysis:
Statement (A) is True.
Statement (B) is False.
Statement (C) is True.
Statement (D) is False.
The true statements are (A) and (C).
Selecting the Correct Option
We need to identify the option that lists only the true statements, which are (A) and (C). Let's examine the given choices:
Option Number
Statements
1
(B) and (D) only
2
(A) and (C) only
3
(A) and (B) only
4
(C) and (D) only
Option 2 correctly includes statements (A) and (C), which we have determined to be true. Therefore, Option 2 is the correct choice.
