Which of the following statements regarding BFS and DFS on an undirected simple graph G is/are TRUE?

Correct Answer: (B), (C), (D)A — FALSE: DFS does not guarantee shortest paths. BFS does (for unweighted graphs).B — TRUE: In an undirected graph, all non-tree edges in a DFS tree are back edges (connecting a vertex to an ancestor). No cross or forward edges exist for undirected graphs under DFS.C — TRUE: In a BFS tree, if (u,v) is a non-tree edge, then |d(s,u) − d(s,v)| ≤ 1. If they differed by ≥ 2, the edge would have been discovered as a tree edge earlier — contradiction.D — TRUE: Both BFS and DFS count connected components by counting how many times the main loop initiates a new traversal from an unvisited vertex.

GATE-CS is a competitive examination conducted in India. This question is from the 2025 GATE-CS Algorithm paper.

How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2025 question covers Graph Traversals (BFS and DFS) topic.

What is the difficulty level of this question?

This GATE-CS 2025 Algorithm question has a medium difficulty level and is marked as an important question.

Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

GATE-CS Algorithm 2025 - Which of the following...

The given DFS algorithm computes d[v] (discovery time) and f[v] (finishing time) for each vertex. Th…

HARD2026GATE-CSAlgorithm

An undirected simple graph G(V,E) is 2-colorable if there exists c: V --> {0,1} such that for every …

MEDIUM2026GATE-CSAlgorithm

Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of …

HARD2025GATE-CSAlgorithm

someAlgo(G): (1) BFS from any v, find farthest vertex u. (2) BFS from u, find farthest vertex z. (3)…

MEDIUM2025GATE-CSAlgorithm

The number of edges present in the forest generated by the DFS traversal of an undirected graph G wi…

EASY2024GATE-CSAlgorithm

Let G be a directed graph and T a DFS spanning tree in G rooted at vertex v. Suppose T is also a BFS…

HARD2024GATE-CSAlgorithm

Which of the following statements regarding BFS and DFS on an undirected simple graph G is/are TRUE?

Master GATE-CS with Our Test Series

More Questions from Graph Traversals (BFS and DFS)

Frequently Asked Questions

Which of the following statements regarding BFS and DFS on an undirected simple graph G is/are TRUE?

Master GATE-CS with Our Test Series

More Questions from Graph Traversals (BFS and DFS)

Frequently Asked Questions