Your question is Cycle Detection in Graphs. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Durlston Partners' research dependency graph represents relationships between computed artifacts and the inputs they depend on. Given this directed graph, determine whether any dependency cycle exists.
Implement has_cycle(graph). The graph is an adjacency-list dictionary where each key is a node and its value is a list of nodes it directly points to. Nodes may be disconnected, may appear only as neighbors, and may be represented by any hashable Python value. Return True if the graph contains at least one directed cycle, including a self-loop; otherwise return False.
Use an iterative traversal so the algorithm does not fail because of Python's recursion-depth limit on long dependency chains.
graph, a dictionary mapping hashable node labels to lists of neighboring node labels. A neighbor not present as a key is treated as a terminal node with no outgoing edges.def has_cycle(graph):