Why won't the algorithm to detect cycles in undirected graphs work to detect cycles in directed graph

12 Views Asked by At

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

0

There are 0 best solutions below