forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcheck_cycle.py
53 lines (44 loc) · 1.54 KB
/
check_cycle.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
"""
Program to check if a cycle is present in a given graph
"""
def check_cycle(graph: dict) -> bool:
"""
Returns True if graph is cyclic else False
>>> check_cycle(graph={0:[], 1:[0, 3], 2:[0, 4], 3:[5], 4:[5], 5:[]})
False
>>> check_cycle(graph={0:[1, 2], 1:[2], 2:[0, 3], 3:[3]})
True
"""
# Keep track of visited nodes
visited: set[int] = set()
# To detect a back edge, keep track of vertices currently in the recursion stack
rec_stk: set[int] = set()
for node in graph:
if node not in visited:
if depth_first_search(graph, node, visited, rec_stk):
return True
return False
def depth_first_search(graph: dict, vertex: int, visited: set, rec_stk: set) -> bool:
"""
Recur for all neighbours.
If any neighbour is visited and in rec_stk then graph is cyclic.
>>> graph = {0:[], 1:[0, 3], 2:[0, 4], 3:[5], 4:[5], 5:[]}
>>> vertex, visited, rec_stk = 0, set(), set()
>>> depth_first_search(graph, vertex, visited, rec_stk)
False
"""
# Mark current node as visited and add to recursion stack
visited.add(vertex)
rec_stk.add(vertex)
for node in graph[vertex]:
if node not in visited:
if depth_first_search(graph, node, visited, rec_stk):
return True
elif node in rec_stk:
return True
# The node needs to be removed from recursion stack before function ends
rec_stk.remove(vertex)
return False
if __name__ == "__main__":
from doctest import testmod
testmod()