Interview Camp
Technique: Detecting Cycles using DFS
Level: Medium
Given a graph, find if there is a cycle.
Questions to Clarify:
Q. Is this a directed or undirected graph?
A. It is a directed graph.
Solution:
We do a Depth First Search (DFS). During the DFS, we visit nodes. This involves going through the
node's neighbors.
While visiting a node N, let's say we find that one of N's neighbors - P - is already in the VISITING state.
This means P is in the path from root to N, which means we have found a cycle. P and N are part of this
cycle.
Note that we look for neighbors in the VISITING state and not VISITED state. This is because if a
neighbor X has been visited already, we have processed all the nodes from X, and there is no path
from X to N.
© 2017 Interview Camp (interviewcamp.io)
Interview Camp
Pseudocode:
// modify the dfsVisit function to check neighbors in VISITING state
hasCycleDfsVisit(Node, Target)
Node.state = VISITING
For each neighbor:
if Neighbor is UNVISITED
perform dfsVisit on Neighbor
if dfsVisit returned true, cycle found, return true and exit
else if Neighbor is VISITING
cycle found, return true and exit
Node.state = VISITED
Target not found, return false
Test Cases:
Edge Cases: Empty graph
Base Cases: 1 node, 2 nodes connected/disconnected
Regular Cases: Has cycle, No cycle
Time Complexity: O(V + E)
Space Complexity: O(V)
© 2017 Interview Camp (interviewcamp.io)
Interview Camp
public static boolean hasCycle(Graph graph) {
for(Node node : graph.getNodes()) {
if (node.getState() == State.UNVISITED && hasCycleDfsVisit(node))
return true;
}
return false;
}
public static boolean hasCycleDfsVisit(Node node) {
node.setState(State.VISITING);
for (Node neighbor: node.getNeighbors()) {
if (neighbor.getState() == State.UNVISITED &&
hasCycleDfsVisit(neighbor))
return true;
else if (neighbor.getState() == State.VISITING)
return true;
}
node.setState(State.VISITED);
return false;
}
/*
* Helper Code. Ask interviewer before implementing.
*/
public enum State {
UNVISITED,
VISITING,
VISITED;
}
public class Graph {
List<Node> nodes;
public Graph(List<Node> nodes) {
super();
this.nodes = nodes;
}
public void addNode(Node node) {
nodes.add(node);
}
public List<Node> getNodes() {
return nodes;
}
© 2017 Interview Camp (interviewcamp.io)
Interview Camp
public class Node {
List<Node> neighbors;
int data;
State state;
public Node(int data) {
super();
this.data = data;
state = State.UNVISITED;
neighbors = new ArrayList<Node>();
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public void setState(State state) {
this.state = state;
}
public State getState() {
return state;
}
public void addNeighbor(Node node) {
neighbors.add(node);
}
public List<Node> getNeighbors() {
return neighbors;
}
}
© 2017 Interview Camp (interviewcamp.io)
