fork(4) download 
  1. graph = {'A': ['B', 'C'],
  2.          'B': ['A', 'D', 'E'],
  3.          'C': ['A', 'F'],
  4.          'D': ['B'],
  5.          'E': ['B', 'F'],
  6.          'F': ['C', 'E'],
  7.          'G': ['K']}
  8.  
  9.  
  10. def push(array, item):
  11.     array.insert(0, item)
  12.  
  13. def pop(array):
  14.     return array.pop(0)
  15.  
  16. def dfs_paths(graph, start, goal):
  17.     paths = []
  18.     stack = [(start, [start])]
  19.  
  20.     while stack:
  21.         (vertex, path) = pop(stack)
  22.         vertices = graph[vertex]
  23.  
  24.         for next_vertex in (set(vertices) - set(path)):
  25.             new_path = path + [next_vertex]
  26.  
  27.             if next_vertex == goal:
  28.                 paths.append(new_path)
  29.             else:
  30.                 push(stack, (next_vertex, new_path))
  31.  
  32.     return paths
  33.  
  34. print dfs_paths(graph, 'A', 'F') # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
  35. def dfs_paths_rec(graph, start, goal, path=[]):
  36.     if start == goal:
  37.         path.append(start)
  38.         return path
  39.  
  40.     paths = []
  41.     for next in set(graph[start]) - set(path):
  42.         new_path = dfs_paths_rec(graph, next, goal, path + [next])
  43.         paths.append(new_path)
  44.  
  45.     return paths
  46.  
  47. print dfs_paths_rec(graph, 'A', 'F')
  48.  
  49. # [[[[[['C', 'A', 'B', 'E', 'F', 'F']], []]], ['C', 'F', 'F']], [[[['B', 'A', 'C', 'F', 'F']]], [['B', 'E', 'F', 'F']], []]]
Success #stdin #stdout 0.01s 7736KB
comments (?)
stdin 
Standard input is empty
stdout 
[['A', 'B', 'E', 'F'], ['A', 'C', 'F']]
[[[[[['C', 'A', 'B', 'E', 'F', 'F']], []]], ['C', 'F', 'F']], [[[['B', 'A', 'C', 'F', 'F']]], [['B', 'E', 'F', 'F']], []]]
https://ideone.com/ekfFDP
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!