Skip to content

Instantly share code, notes, and snippets.

@Fredpwol
Created June 20, 2021 17:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Fredpwol/f819e4daa0f85ed3b2e02b94a8171b76 to your computer and use it in GitHub Desktop.
Save Fredpwol/f819e4daa0f85ed3b2e02b94a8171b76 to your computer and use it in GitHub Desktop.
Find circle in a graph from a start point
def depth_first_search(map, key, start):
if key == None: return []
key = key.lower() if key.lower() in map else key.upper()
if not key in map: return []
if map[key] == None: return []
res = []
for point in map[key]:
if point.lower() == start.lower():
return [point]
path = depth_first_search(map, point, start)
if len(path) != 0:
for circle in path:
res.append(point + circle)
return res
def find_cycle_in_path(map, start):
if map == None: return []
start = start.lower() if start.lower() in map else start.upper()
if not start in map: return []
if map[start] == None: return []
res = []
for point in map[start]:
search = depth_first_search(map, point, start)
if len(search) != 0:
for circle in search:
res.append(start + point + circle)
return res
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment