Skip to content

Instantly share code, notes, and snippets.

@sadi304
Created March 23, 2019 16:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sadi304/752b6e38e46aa24fcd9022d29398b8e1 to your computer and use it in GitHub Desktop.
Save sadi304/752b6e38e46aa24fcd9022d29398b8e1 to your computer and use it in GitHub Desktop.
Detect cycle in a directed graph
#
# detect cycle
# in a directed graph
# sadi304
#
def dfs(G, u, color, found_cycle):
if found_cycle[0]:
return
color[u] = "gray"
for v in G[u]:
if color[v] == "gray":
found_cycle[0] = True
return
if color[v] == "white":
dfs(G, v, color, found_cycle)
color[u] = "black"
def cycleCheck(G):
color = { u : "white" for u in G } # mark as white, that is: inititally nodes are not visited
found_cycle = [False]
for u in G:
if color[u] == "white":
dfs(G, u, color, found_cycle)
if found_cycle[0]:
break
return found_cycle[0]
graphWithCycle = {
0: [1],
1: [2],
2: [3],
3: [4],
4: [5],
5: [3]
}
hasCycle = cycleCheck(graphWithCycle)
print(hasCycle)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment