Detect cycle and remove cycle in directed graph

A graph is a data structure that consists of a set of nodes (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 cycle and remove cycle in directed graph.

To detect cycle in a directed graph, we use backtracking technique in depth first search. 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 recursive 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 cycles 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.




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.js

What is the method to detect cycle in a directed graph?

You can use backtracking in depth first search.

What is the method to remove a cycle in a directed graph

The algorithms to remove cycles completely in a directed graph can be complicated. If you just remove one cycle, you can use brute force. Remove one edge at a time. Use detect cycle method to check whether the cycle is gone. If not, move to the next edge.

Comments are closed