So here's my code here, it's meant to detect cycles from undirected graphs, sources say it won't work on detecting cycles on directed graphs. But I really can't think of any scenario where it don't work through?:
# Input: a graph G = (V, E) with n vertices and m edges
# Output: true if G contains a cycle, false otherwise
# Initialize a list of boolean values to mark the visited vertices
visited = [False] * n
# Initialize a list of integers to store the parent of each vertex in the DFS tree
parent = [-1] * n
# Define a recursive function to perform DFS from a given vertex
def dfs(v):
# Mark the current vertex as visited
visited[v] = True
# Loop through the adjacent vertices of v
for u in G.adj(v):
# If u is not visited, then recursively explore u and update its parent
if not visited[u]:
parent[u] = v
dfs(u)
# If u is visited and u is not the parent of v, then a cycle is found
elif u != parent[v]:
return True
# Return false if no cycle is found
return False
# Loop through all the vertices of the graph
for v in V:
# If v is not visited, then perform DFS from v
if not visited[v]:
# If DFS returns true, then a cycle is found
if dfs(v):
return True
# Return false if no cycle is found in the graph
return False
I tried it on most directed graphs I tested, it worked well?
for example, I tested it on directed graph
G = {'A': ['B', 'C'],
'B': ['D'],
'C': ['A'],
'D': ['C']}
and it successfully detect the cycle using the "undirected cycle" algorithm