-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfsPaths.py
33 lines (31 loc) · 1.05 KB
/
bfsPaths.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
Given a graph with or without cycles, a source vertex s and a destination vertex d,
print all paths from given s to d.
The algorithm follows BFS or Breadth first search strategy
"""
def all_paths_bfs(graph, start, goal):
queue = [(start, [start])]
visited = {}
visited[start] = True
paths = []
while queue:
(vertex, path) = queue.pop(0)
nodes = graph[vertex]
for i in range(len(nodes)-1,-1,-1):
next_node = nodes[i]
if next_node not in visited or visited[next_node] is False:
visited[next_node] = True
if next_node == goal:
paths.append(path + [next_node])
visited[next_node] = False # Since we want all paths to this node
else:
queue.append((next_node, path + [next_node]))
return paths
# Test
graph = {'A': ['A','B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']}
print all_paths_bfs(graph, 'C', 'F')