depth first search stack
# HAVE USED ADJACENY LIST
class Graph:
def __init__(self,lst=None):
self.lst=dict()
if lst is None:
pass
else:
self.lst=lst
def find_path(self,start,end):
self.checklist={}
for i in self.lst.keys():
self.checklist[i]=False
self.checklist[start]=True
store,extra=(self.explore(start,end))
if store==False:
print('No Path Found')
else:
print(extra)
def explore(self,start,end):
while True:
q=[]
#print(self.checklist,q)
q.append(start)
flag=False
for i in self.lst[start]:
if i==end:
q.append(i)
return True,q
if self.checklist[i]:
pass
else:
flag=True
self.checklist[i]=True
q.append(i)
break
if flag:
store,extra=self.explore(q[-1],end)
if store==False:
q.pop()
if len(q)==0:return False
return self.explore(q[-1],end)
elif store==None:
pass
elif store==True:
q.pop()
q.extend(extra)
return True,q
else:
return False,None
def __str__(self):return str(self.lst)
if __name__=='__main__':
store={1: [2, 3, 4], 2: [3, 1], 3: [2, 1], 4: [5, 8, 1], 5: [4, 6, 7], 6: [5, 7, 9, 8], 7: [5, 6], 8: [4, 6, 9], 9: [6, 8, 10], 10: [9],11:[12,13]}
a=Graph(store)
a.find_path(1,11) # No Path Found
a.find_path(1,6)# [1, 4, 5, 6]
a.find_path(3,10) # [3, 2, 1, 4, 5, 6, 9, 10]
a.find_path(4,10)# [4, 5, 6, 9, 10]
print(a) #
DFS-iterative (G, s): //Where G is graph and s is source vertex
let S be stack
S.push( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = S.top( )
S.pop( )
//Push all the neighbours of v in stack that are not visited
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited
DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)
# An Iterative Python program to do DFS traversal from
# a given source vertex. DFS(int s) traverses vertices
# reachable from s.
# This class represents a directed graph using adjacency
# list representation
class Graph:
def __init__(self,V): # Constructor
self.V = V # No. of vertices
self.adj = [[] for i in range(V)] # adjacency lists
def addEdge(self,v, w): # to add an edge to graph
self.adj[v].append(w) # Add w to v’s list.
# prints all not yet visited vertices reachable from s
def DFS(self,s): # prints all vertices in DFS manner from a given source.
# Initially mark all verices as not visited
visited = [False for i in range(self.V)]
# Create a stack for DFS
stack = []
# Push the current source node.
stack.append(s)
while (len(stack)):
# Pop a vertex from stack and print it
s = stack[-1]
stack.pop()
# Stack may contain same vertex twice. So
# we need to print the popped item only
# if it is not visited.
if (not visited[s]):
print(s,end=' ')
visited[s] = True
# Get all adjacent vertices of the popped vertex s
# If a adjacent has not been visited, then push it
# to the stack.
for node in self.adj[s]:
if (not visited[node]):
stack.append(node)
# Driver program to test methods of graph class
g = Graph(5); # Total 5 vertices in graph
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(1, 4);
print("Following is Depth First Traversal")
g.DFS(0)