Detect and remove a cycle in a directed graph

A graph is a data structure that consists of a set of nodes (aka vertices) connected by edges. A graph is cyclic if the graph comprises a path that starts from a node and ends at the same node. In this post, a simplified solution is provided to detect and remove a cycle in a directed graph.

To detect cycle in a directed graph, we use backtracking technique. We define a variable backtrack to keep track this. The initial value is false for each node. When using depth first search to visit each node, the value of backtrack for the visited node is set to be true. Next is to visit this node’s neighbors. If there is cycle, the same node will be visited again and dfs helper method returns true without backtracking. If there is no cycle, the call stack will return and the backtrack value will be reset to false. When the backtrack is false and the node is already visited, dfs helper method will return false and no cycle is detected.

detect cycle in graph

After a cycle is detected, next is to remove cycle in graph. However it is a complicated problem. You can refer the reduction of Directed Cyclic Graph for details. The problem cannot be solved in an hour interview. But if you assume there is only one cycle, you can apply a simple brute force solution. That is to remove one edge at a time and call detect cycle to check whether the cycle is gone. The following is the source code to


remove edge in directed graph


Facebook Interview Question:
class DirectedGraphNode {
int label;
List neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<>();
}
}
check if there is a cycle in a directed graph, if there is a cycle, remove the cycle.

Java

JavaScript

Python

Output:
has cycle: true
remove edge: 0,1
has cycle: false

O Notation:
Time complexity: O(E*(V+E))
Space complexity: O(V)
V is number of vertices, E is number of edges.

Download GraphDetectCycleAndRemove.java
Download GraphDetectCycleAndRemove.js
Download GraphDetectCycleAndRemove.py
Convert Graph To Tree (GitHub)

Comments are closed