Traversal#
Question#
Demonstrate Graph Traversal Algorithms.
Solution#
from collections import deque
def bfs(g, start):
queue, enqueued = deque([(None, start)]), set([start])
while queue:
parent, n = queue.popleft()
yield parent, n
new = set(g[n]) - enqueued
enqueued |= new
queue.extend([(n, child) for child in new])
def dfs(g, start):
stack, enqueued = [(None, start)], set([start])
while stack:
parent, n = stack.pop()
yield parent, n
new = set(g[n]) - enqueued
enqueued |= new
stack.extend([(n, child) for child in new])
def shortest_path(g, start, end):
parents = {}
for parent, child in bfs(g, start):
parents[child] = parent
if child == end:
revpath = [end]
while True:
parent = parents[child]
revpath.append(parent)
if parent == start:
break
child = parent
return list(reversed(revpath))
return None # or raise appropriate exception
if __name__ == '__main__':
# a sample graph
graph = {'A': ['B', 'C','E'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F', 'D'],
'F': ['C']}
for node in bfs(graph,'A'):
print(node)