print "GRAPH TRAVERSLS-DEPTH FIRST SEARCH"
graph={'A': ['G','B'],
'B': ['C'],
'C': ['E','D'],
'D': [],
'E': ['D','F'],
'F': ['A'],
'G': ['F']}#Input the graph details using a sequence data structure
def dfs(graph,start):
path=[]#Initially the path is empty, as no nodes are visited
stack=[start]#The starting node is pushed into the stack
while stack!=[]:
visited=stack.pop()#The node is marked as visited
if visited not in path:
path.append(visited)#The node is added to the path
for w in reversed(graph[visited]):#The node is checked to see if it has any adjacent nodes.
if w not in path:
stack.append(w)#Adjacent nodes if any without being visited are added to the stack
return path
print "path=",dfs(graph,'A')#The sequence and the starting nodes are given as input
print "GRAPH TRAVERSALS-BREADTH FIRST SEARCH"
graph={'A': set(['G','B']),
'B': set(['C']),
'C': set(['D','E']),
'D': set([]),
'E': set(['D','F']),
'F': set(['A']),
'G': set(['F'])}#Input the graph information
def bfs(graph,start):
path=[]#Initially path is empty as no nodes are visited
queue=[start]#The start node is added to the queue
while queue:
v=queue.pop(0)#Always the first node is only popped
if v not in path:
path+=[v]#The popped node is added to the path
queue+=graph[v]#The adjacent nodes of the visited nodes are inserted in the queue
return path
print "path=",bfs(graph,'A')