1.

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»

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.


Discussion

No Comment Found

Related InterviewSolutions