GATE Overflow Test Series | Algorithms | Test 2 | Question: 14

Question

Which of the following statements is/are TRUE?  (Mark all the correct options)

• A. If in a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges, then the number of connected components in $G$ is $n-k-1$
• B. The tightest upper bound on the worst case time complexity in determining the existence of a cycle in an undirected graph $G = (V,E)$ is $\Theta(|V|)$
• C. The tightest upper bound on the worst case time complexity in determining the existence of a cycle in an undirected graph $G = (V,E)$ is $\Theta(|V| + |E|)$
• D. In a connected graph $G = (V,E)$ with $n$ vertices DFS will yield $n-1$ tree edges

Comments

Option D is TRUE only if the graph is undirected. If the graph is directed then dfs tree may become dfs forest(that is some nodes are not reachable from source) and no of tree edges will get decreased not n-1

---

same doubt

---

If I’m thinking correct then for Option B,

in an undirected graph during BFS first $|V| – 1$ edges can form a tree and any extra edge will form a cycle. So we just have to traverse at most for $|V|$ edges.

Now the time complexity of BFS is $O(|V| + |E|)$ but the $|E|$ in this case will be $|V|$

So, $O(|V| + |V|)$ = $O(|V|)$

Answer 1

If in a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges, then the number of connected components in $G$ is $n-k$ as each connected component of $l$ vertices gives $l-1$ tree edges. i.e.,
$$\displaystyle k = \sum_{i=1}^d l_i -1 = n - d,$$
where $d$ is the number of connected components in $G.$ So, $d = n - k$ and option A is false.

Option B is true and C is false as we can use BFS for cycle detection and though the time complexity of BFS is $\Theta(|V| + |E|),$ we can do this in $\Theta(|V|)$ as once a cycle is detected we can stop the BFS and this should happen within $O(|V|)$ time.

Option D is true.

Comments

Option D specifically mentions ‘Tree Edges’ @ayush.5 @Bikash Singh

---

Option B

In worst case cycle could be at end of graph for which entire BFS OR DFS has to run. Thus worst case complexity will be O(V + E). But  E = V for such graph. Hence time complexity will not go over O(V).

---

We can claim the same tightest upper bound on the worst case time complexity in determining the existence of a cycle in an directed graph as well, right?

Answer 2

For option $A$

https://gateoverflow.in/3759/gate2005-it-14

For option $B$

In a DFS of an undirected graph G, every edge of G is either a tree edge or a back edge.

If we find a back edge then there is a cycle. Now if we ever see $|V|$ distinct edges, we must have seen a back edge because in an acyclic(undirected) forest, $|E|<=V-1$

If $B$ is true, then $C$ is false.

For option $D$

False.

Comments

Basic
As per the link we can detect cycle using both DFS and BFS for **UNDIRECTED GRAPH**
But for **DIRECTED graph we can use only DFS**--https://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs
Second
Why option A is true not B ?

the worst case either DFS or BFS takes O(V+E)time complexity

---

@kushagra, for option D, every vertex will be visited exactly once and graph is connected so there should be n-1 edges. How is D wrong? Can you give an example?