CUET PG 2025 — Computer PYQ

Q: How do I solve CUET PG 2025 Computer questions?

Practice CUET PG 2025 Computer previous year questions with step-by-step solutions on Mathem Solvex. Each question includes a detailed explanation and video solution to help you master the concept quickly.

Q: What is the difficulty level of CUET PG Computer questions?

CUET PG Computer questions range from moderate to advanced difficulty. Consistent practice with official previous year papers and topic-wise drills on Mathem Solvex is the most effective preparation strategy.

Q: Are CUET PG previous year papers available for free?

Yes. Mathem Solvex provides free access to CUET PG previous year question papers and topic-wise PDFs. You can download them or attempt them as timed live mock tests directly on the platform.

Question

CUET PG 2025 — Computer PYQ

CUET PG | Computer | 2025

Which of the following is not an application of DFS?

Choose the correct answer:

Explanation

The correct answer is

Finding minimum distance to a node in an unweighted graph optimally

Answer 1

Understanding Depth First Search (DFS) Applications

Depth First Search (DFS) is a fundamental graph traversal algorithm. It explores as far as possible along each branch before backtracking. Let's examine the provided options to see which one is not a typical or optimal application of DFS.

1. Topological Sort Application

DFS is effectively used for Topological Sorting. In a directed acyclic graph (DAG), a topological sort is a linear ordering of its vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. DFS achieves this by tracking the finishing times of nodes; nodes finished later appear earlier in the topological sort.

2. Determining Strongly Connected Components (SCCs)

DFS is a core component in algorithms designed to find Strongly Connected Components (SCCs) in a directed graph. Algorithms like Kosaraju's algorithm and Tarjan's algorithm utilize DFS traversals (often two passes) to identify these components, where each component consists of a set of vertices such that there is a path between any pair of vertices within the component.

3. Finding Minimum Distance in Unweighted Graphs

Finding the minimum distance (in terms of the number of edges) from a source node to all other reachable nodes in an unweighted graph is optimally solved using Breadth First Search (BFS). BFS explores the graph layer by layer, guaranteeing that the first time a node is reached, it is via the shortest path from the source. DFS, on the other hand, explores deeply down a path. While DFS can find a path, it does not guarantee finding the shortest path first in an unweighted graph, making it unsuitable for optimal minimum distance calculation.

4. Solving Maze Problems

DFS is a common and effective algorithm for solving maze problems. By treating the maze as a graph where corridors are edges and junctions/cells are nodes, DFS can explore potential paths from the start to the end. When it hits a dead end, it backtracks and tries another path, systematically searching the maze until a solution is found or all possibilities are exhausted.

Conclusion on DFS Applications

Based on the analysis, while DFS is suitable for Topological Sort, finding SCCs, and solving mazes, it is not the optimal algorithm for finding the minimum distance to a node in an unweighted graph. BFS is the preferred algorithm for this specific task.

Answer 2

Understanding Depth First Search (DFS) Applications

Depth First Search (DFS) is a fundamental graph traversal algorithm. It explores as far as possible along each branch before backtracking. Let's examine the provided options to see which one is not a typical or optimal application of DFS.

1. Topological Sort Application

DFS is effectively used for Topological Sorting. In a directed acyclic graph (DAG), a topological sort is a linear ordering of its vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. DFS achieves this by tracking the finishing times of nodes; nodes finished later appear earlier in the topological sort.

2. Determining Strongly Connected Components (SCCs)

DFS is a core component in algorithms designed to find Strongly Connected Components (SCCs) in a directed graph. Algorithms like Kosaraju's algorithm and Tarjan's algorithm utilize DFS traversals (often two passes) to identify these components, where each component consists of a set of vertices such that there is a path between any pair of vertices within the component.

3. Finding Minimum Distance in Unweighted Graphs

Finding the minimum distance (in terms of the number of edges) from a source node to all other reachable nodes in an unweighted graph is optimally solved using Breadth First Search (BFS). BFS explores the graph layer by layer, guaranteeing that the first time a node is reached, it is via the shortest path from the source. DFS, on the other hand, explores deeply down a path. While DFS can find a path, it does not guarantee finding the shortest path first in an unweighted graph, making it unsuitable for optimal minimum distance calculation.

4. Solving Maze Problems

DFS is a common and effective algorithm for solving maze problems. By treating the maze as a graph where corridors are edges and junctions/cells are nodes, DFS can explore potential paths from the start to the end. When it hits a dead end, it backtracks and tries another path, systematically searching the maze until a solution is found or all possibilities are exhausted.

Conclusion on DFS Applications

Based on the analysis, while DFS is suitable for Topological Sort, finding SCCs, and solving mazes, it is not the optimal algorithm for finding the minimum distance to a node in an unweighted graph. BFS is the preferred algorithm for this specific task.