Cycle Detection in Undirected Graph in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a cycle in an undirected graph?

A cycle is a path that starts and ends at the same vertex with no repeated edges or vertices (except the start/end vertex).

beginner

Which data structure is commonly used to detect cycles in an undirected graph?

Depth-First Search (DFS) is commonly used to detect cycles by checking if a visited vertex is encountered again and is not the parent of the current vertex.

intermediate

In cycle detection using DFS, why do we check if the visited vertex is not the parent?

Because in an undirected graph, the edge to the parent is always visited, so revisiting the parent does not mean a cycle. We look for visited vertices other than the parent to confirm a cycle.

intermediate

What is the time complexity of cycle detection in an undirected graph using DFS?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and edge is visited once.

advanced

How does the Union-Find (Disjoint Set) data structure help in cycle detection?

Union-Find keeps track of connected components. When adding an edge, if both vertices belong to the same set, a cycle is detected. Otherwise, the sets are united.

What indicates a cycle during DFS traversal in an undirected graph?

A Visiting a vertex that is already visited and is not the parent

B Visiting a vertex for the first time

C Visiting the parent vertex again

D No edges left to explore

A cycle is detected if a visited vertex is found again during DFS and it is not the parent of the current vertex.

Which of the following is NOT true about cycle detection in undirected graphs?

A DFS can be used to detect cycles

B A cycle can be detected by checking only the degree of vertices

C Union-Find can detect cycles efficiently

D A cycle must include at least one vertex repeated twice

Checking only the degree of vertices is not sufficient to detect cycles in undirected graphs.

What is the role of the 'parent' parameter in DFS cycle detection?

A To avoid counting the edge back to the parent as a cycle

B To mark the starting vertex

C To count the number of edges

D To store the depth of the vertex

The parent parameter helps ignore the edge leading back to the parent vertex, which is not a cycle.

What is the worst-case time complexity of cycle detection using Union-Find?

A O(V + E)

B O(E log V)

C O(V^2)

D O(E α(V)) where α is the inverse Ackermann function

Union-Find operations run in almost constant time, O(α(V)), making total complexity O(E α(V)) for E edges.

If a graph has no cycles, what kind of graph is it called?

A Disconnected graph

B Complete graph

C Tree

D Directed graph

A connected graph with no cycles is called a tree.

Explain how DFS can be used to detect a cycle in an undirected graph.

Think about revisiting vertices during traversal.

Describe how the Union-Find data structure detects cycles when edges are added.

Focus on connected components and set membership.