py_graph_cycle_detector · Python

▶ Aprender py_graph_cycle_detector (Python) paso a paso · explicación de py_graph_cycle_detector

Código línea a línea

Tres columnas: el código, el trozo del subject o del main que obliga a escribir esa línea, y el por qué.

py_graph_cycle_detector.py

Código	Subject	Por qué
`def py_graph_cycle_detector(graph: dict[int, list[int]]) -> bool:`	`def py_graph_cycle_detector(graph: dict[int, list[int]]) -> bool:`	Firma del subject: aquí el nombre de la función lleva el `py_`.
`state = {}`	Correctly handle graphs with multiple disconnected components.	Estado por nodo: sin entrada = no visto, 1 = en el camino actual, 2 = terminado. Compartido por todos los arranques.

`def visit(node):`	directed graph contains at least one cycle	DFS anidada: puede usar `graph` y `state` sin pasarlos.
`if state.get(node) == 1:`	Return True if the directed graph contains a cycle.	Vuelvo a un nodo que sigue en el camino actual → ciclo.
`return True`		Propago el `True` hacia arriba sin seguir buscando.
`if state.get(node) == 2:`		Ya explorado del todo sin ciclo: no hace falta repetirlo.
`return False`	Return False if the graph is acyclic or if the input graph dictionary is empty.	Sin ciclo por aquí. En la última, ningún arranque lo encontró: con `{}` el bucle no entra y devuelvo `False` directo.
`state[node] = 1`		Entro: marco "en el camino".
`for nxt in graph.get(node, []):`	values are lists of integer neighbor node IDs	`get` con `[]`: un vecino que no es clave del dict no tiene salidas.
`if visit(nxt):`		Bajo por cada vecino; cualquier ciclo abajo me sirve.
`return True`		Propago el `True` hacia arriba sin seguir buscando.
`state[node] = 2`		Salgo: todo lo que cuelga de aquí está limpio.
`return False`	Return False if the graph is acyclic or if the input graph dictionary is empty.	Sin ciclo por aquí. En la última, ningún arranque lo encontró: con `{}` el bucle no entra y devuelvo `False` directo.

`for node in graph:`	Correctly handle graphs with multiple disconnected components.	Arranco desde cada nodo: así llego a componentes que no se tocan entre sí.
`if visit(node):`		Un ciclo en cualquier componente basta.
`return True`		Propago el `True` hacia arriba sin seguir buscando.
`return False`	Return False if the graph is acyclic or if the input graph dictionary is empty.	Sin ciclo por aquí. En la última, ningún arranque lo encontró: con `{}` el bucle no entra y devuelvo `False` directo.