GATE 2024 CS (CS1) – Question 60

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

The number of edges present in the forest generated by the DFS traversal of an undirected graph $G$ with 100 vertices is 40. The number of connected components in $G$ is _________

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 60

Explanation

A spanning forest with c components on n vertices has n − c edges. So 100 − c = 40, giving c = 60.