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
(graph: dict)
| 4 | |
| 5 | |
| 6 | def check_cycle(graph: dict) -> bool: |
| 7 | """ |
| 8 | Returns True if graph is cyclic else False |
| 9 | >>> check_cycle(graph={0:[], 1:[0, 3], 2:[0, 4], 3:[5], 4:[5], 5:[]}) |
| 10 | False |
| 11 | >>> check_cycle(graph={0:[1, 2], 1:[2], 2:[0, 3], 3:[3]}) |
| 12 | True |
| 13 | """ |
| 14 | # Keep track of visited nodes |
| 15 | visited: set[int] = set() |
| 16 | # To detect a back edge, keep track of vertices currently in the recursion stack |
| 17 | rec_stk: set[int] = set() |
| 18 | return any( |
| 19 | node not in visited and depth_first_search(graph, node, visited, rec_stk) |
| 20 | for node in graph |
| 21 | ) |
| 22 | |
| 23 | |
| 24 | def depth_first_search(graph: dict, vertex: int, visited: set, rec_stk: set) -> bool: |
nothing calls this directly
no test coverage detected