Created
April 6, 2020 02:24
-
-
Save nhudinhtuan/8451b2735a8462f98a6e8eeff5d94fce to your computer and use it in GitHub Desktop.
Detect cycle in undirected graph
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # graph is represented by adjacency list: List[List[int]] | |
| # DFS to detect cyclic | |
| def is_cyclic_undirected_graph(graph): | |
| # set is used to mark visited vertices | |
| visited = set() | |
| def is_cyclic_recur(current_vertex, parent): | |
| # mark it visited | |
| visited.add(current_vertex) | |
| # Recur for all the vertices adjacent to current_vertex | |
| for v in graph[current_vertex]: | |
| # If the vertex is not visited then recurse on it | |
| if v not in visited: | |
| if is_cyclic_recur(v, current_vertex): | |
| return True | |
| elif v != parent: | |
| # found a cycle | |
| return True | |
| return False | |
| # call recur for all vertices | |
| for u in range(len(graph)): | |
| # Don't recur for u if it is already visited | |
| if u not in visited: | |
| if is_cyclic_recur(u, -1): | |
| return True | |
| return False |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment