Cycle detection in directed graph - cocoder39/coco39_LC GitHub Wiki

Reference: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/

Option 1: DFS

Snap interview problem: this solution can be used to solve a variant of LC Course Schedule problem. Eg, given prerequisites, and a target course, find the ordering to get the course and detect loop if there exists loop.

tradeoffs between topological sort vs dfs: topological sort is good at inferring the ordering for all courses while dfs is efficient to infer the ordering for a specific course

subproblem 1 - get ordering: which can be solved by regular DFS with a visited set subproblem 2 - loop detection: check if next node to be visited is already in recursion path (indicating a loop is formed)

visited set is superset of recursion path. all nodes in recursion path should be in visited set but visited set could contain nodes in other recursion paths

# Python program to detect cycle
# in a graph

from collections import defaultdict

class Graph():
	def __init__(self,vertices):
		self.graph = defaultdict(list)
		self.V = vertices

	def addEdge(self,u,v):
		self.graph[u].append(v)

	def isCyclicUtil(self, v, visited, recStack):

		# Mark current node as visited and
		# adds to recursion stack
		visited[v] = True
		recStack[v] = True

		# Recur for all neighbours
		# if any neighbour is visited and in
		# recStack then graph is cyclic
		for neighbour in self.graph[v]:
			if visited[neighbour] == False:
				if self.isCyclicUtil(neighbour, visited, recStack) == True:
					return True
			elif recStack[neighbour] == True:
				return True

		# The node needs to be popped from
		# recursion stack before function ends
		recStack[v] = False
		return False

	# Returns true if graph is cyclic else false
	def isCyclic(self):
		visited = [False] * (self.V + 1)
		recStack = [False] * (self.V + 1)
		for node in range(self.V):
			if visited[node] == False:
				if self.isCyclicUtil(node,visited,recStack) == True:
					return True
		return False

g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
if g.isCyclic() == 1:
	print "Graph contains cycle"
else:
	print "Graph doesn't contain cycle"

# Thanks to Divyanshu Mehta for contributing this code

Option 2: topological sort

check in-degree

Option 3: BFS

EG given a directed graph and a target node, find shorted cycle that includes target (Google interview)

bfs traversal + assign a rank to each layer -> once rank collision -> cycle