Created
March 23, 2019 16:36
-
-
Save sadi304/752b6e38e46aa24fcd9022d29398b8e1 to your computer and use it in GitHub Desktop.
Detect cycle in a directed graph
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# | |
# 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