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
(graph: dict, vertex: int, visited: set, rec_stk: set)
| 22 | |
| 23 | |
| 24 | def depth_first_search(graph: dict, vertex: int, visited: set, rec_stk: set) -> bool: |
| 25 | """ |
| 26 | Recur for all neighbours. |
| 27 | If any neighbour is visited and in rec_stk then graph is cyclic. |
| 28 | >>> graph = {0:[], 1:[0, 3], 2:[0, 4], 3:[5], 4:[5], 5:[]} |
| 29 | >>> vertex, visited, rec_stk = 0, set(), set() |
| 30 | >>> depth_first_search(graph, vertex, visited, rec_stk) |
| 31 | False |
| 32 | """ |
| 33 | # Mark current node as visited and add to recursion stack |
| 34 | visited.add(vertex) |
| 35 | rec_stk.add(vertex) |
| 36 | |
| 37 | for node in graph[vertex]: |
| 38 | if node not in visited: |
| 39 | if depth_first_search(graph, node, visited, rec_stk): |
| 40 | return True |
| 41 | elif node in rec_stk: |
| 42 | return True |
| 43 | |
| 44 | # The node needs to be removed from recursion stack before function ends |
| 45 | rec_stk.remove(vertex) |
| 46 | return False |
| 47 | |
| 48 | |
| 49 | if __name__ == "__main__": |
no test coverage detected