Cycle detection in graphs in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding cycle detection in directed graphs

Which method is commonly used to detect cycles in a directed graph?

A Using a minimum spanning tree algorithm

B Breadth-first search with queue tracking

C Depth-first search with recursion stack tracking

D Sorting nodes by their degree

💡 Hint

Think about how to track nodes currently being explored to find back edges.

Depth-first search (DFS) with a recursion stack helps detect back edges, which indicate cycles in directed graphs.

📋 Factual

intermediate

Cycle detection in undirected graphs

What is a common approach to detect cycles in an undirected graph?

A Use Dijkstra's shortest path algorithm

B Use BFS and count the number of edges

C Use topological sorting

D Use DFS and check if a visited node is found that is not the parent

💡 Hint

Consider how revisiting a node that is not the immediate parent indicates a cycle.

In undirected graphs, DFS can detect cycles by checking if a visited node is encountered again and it is not the parent node.

🔍 Analysis

advanced

Detecting cycles using Union-Find

Given an undirected graph, which statement about using Union-Find (Disjoint Set Union) to detect cycles is true?

A If two vertices of an edge belong to the same set, adding that edge creates a cycle

B Union-Find cannot detect cycles in undirected graphs

C Union-Find detects cycles by counting the number of edges

D Union-Find requires sorting edges by weight to detect cycles

💡 Hint

Think about what it means if two nodes are already connected before adding an edge.

If two vertices are already in the same set, connecting them again forms a cycle. Union-Find efficiently tracks connected components.

❓ Comparison

advanced

Comparing cycle detection in directed vs undirected graphs

Which of the following correctly contrasts cycle detection in directed and undirected graphs?

A Directed graphs require tracking recursion stack; undirected graphs require parent tracking in DFS

B Both use the same method of checking visited nodes without parent tracking

C Cycle detection in undirected graphs uses recursion stack; directed graphs use parent tracking

D Cycle detection is not possible in directed graphs

💡 Hint

Consider how direction affects the way cycles are detected.

Directed graphs need recursion stack tracking to detect back edges; undirected graphs detect cycles by checking visited nodes excluding the parent.

❓ Reasoning

expert

Cycle detection output reasoning

Consider the following undirected graph edges: (1-2), (2-3), (3-4), (4-2). After running a cycle detection algorithm using DFS, what is the number of cycles detected?

Data Structures Theory

Edges: [(1,2), (2,3), (3,4), (4,2)]

A 2

B 1

C 0

D 3

💡 Hint

Trace the DFS and identify if multiple cycles or a single cycle exists.

The edges form a single cycle involving nodes 2, 3, and 4. Node 1 connects without forming a cycle.