Scribd
Upload
21 views

Interview Camp: Level: Medium Given A Graph, Find If There Is A Cycle

This document describes how to detect cycles in a directed graph using depth-first search (DFS). It explains that during DFS, if a neighbor node is found in the VISITING state rather than just VISITED, then a cycle has been detected since there is a path from the root to that neighbor.

Uploaded by

abhi74
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views

Interview Camp: Level: Medium Given A Graph, Find If There Is A Cycle

This document describes how to detect cycles in a directed graph using depth-first search (DFS). It explains that during DFS, if a neighbor node is found in the VISITING state rather than just VISITED, then a cycle has been detected since there is a path from the root to that neighbor.

Uploaded by

abhi74
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

 

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) 

You might also like