graphs.check_cycle

Program to check if a cycle is present in a given graph

Functions

check_cycle(→ bool)	Returns True if graph is cyclic else False
depth_first_search(→ bool)	Recur for all neighbours.

Module Contents

graphs.check_cycle.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

graphs.check_cycle.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