Question

For an n-vertex undirected graph, the time required to find a cycle is ____________

(a) O(n)

(b) O(n^2)

(c) O(n+1)

(d) O(logn)

This question was addressed to me during an internship interview.

I'm obligated to ask this question of Trees in division Trees of Discrete Mathematics

Answer 1

Right answer is (a) O(n)

Explanation: The existence of a cycle in directed and undirected graphs can be determined by depth-first search (DFS) of the graph finds an edge that points to an ancestor of the current vertex. In an undirected graph, finding any already visited vertex will indicate a back edge. All the back edges which DFS skips over are part of cycles. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.