1# left to right, pre-order depth first tree search, iterative. O(n) time/space
2def depthFirstSearch(root):
3 st = [root]
4 while st:
5 current = st.pop()
6 print(current)
7 if current.right is not None: st.append(current.right)
8 if current.left is not None: st.append(current.left)
1###############
2#The Algorithm (In English):
3
4# 1) Pick any node.
5# 2) If it is unvisited, mark it as visited and recur on all its
6# adjacent nodes.
7# 3) Repeat until all the nodes are visited, or the node to be
8# searched is found.
9
10
11# The graph below (declared as a Python dictionary)
12# is from the linked website and is used for the sake of
13# testing the algorithm. Obviously, you will have your own
14# graph to iterate through.
15graph = {
16 'A' : ['B','C'],
17 'B' : ['D', 'E'],
18 'C' : ['F'],
19 'D' : [],
20 'E' : ['F'],
21 'F' : []
22}
23
24visited = set() # Set to keep track of visited nodes.
25
26
27##################
28# The Algorithm (In Code)
29
30def dfs(visited, graph, node):
31 if node not in visited:
32 print (node)
33 visited.add(node)
34 for neighbour in graph[node]:
35 dfs(visited, graph, neighbour)
36
37# Driver Code to test in python yourself.
38# Note that when calling this, you need to
39# call the starting node. In this case it is 'A'.
40dfs(visited, graph, 'A')
41
42# NOTE: There are a few ways to do DFS, depending on what your
43# variables are and/or what you want returned. This specific
44# example is the most fleshed-out, yet still understandable,
45# explanation I could find.
1# tree level-by-level traversal. O(n) time/space
2def breadthFirstSearch(root):
3 q = [root]
4
5 while q:
6 current = q.pop(0)
7 print(current)
8 if current.left is not None: q.append(current.left)
9 if current.right is not None: q.append(current.right)
1 DFS-iterative (G, s): //Where G is graph and s is source vertex
2 let S be stack
3 S.push( s ) //Inserting s in stack
4 mark s as visited.
5 while ( S is not empty):
6 //Pop a vertex from stack to visit next
7 v = S.top( )
8 S.pop( )
9 //Push all the neighbours of v in stack that are not visited
10 for all neighbours w of v in Graph G:
11 if w is not visited :
12 S.push( w )
13 mark w as visited
14
15
16 DFS-recursive(G, s):
17 mark s as visited
18 for all neighbours w of s in Graph G:
19 if w is not visited:
20 DFS-recursive(G, w)
1# HAVE USED ADJACENY LIST
2class Graph:
3 def __init__(self,lst=None):
4 self.lst=dict()
5 if lst is None:
6 pass
7 else:
8 self.lst=lst
9 def find_path(self,start,end):
10 self.checklist={}
11 for i in self.lst.keys():
12 self.checklist[i]=False
13 self.checklist[start]=True
14 store,extra=(self.explore(start,end))
15 if store==False:
16 print('No Path Found')
17 else:
18 print(extra)
19 def explore(self,start,end):
20 while True:
21 q=[]
22 #print(self.checklist,q)
23 q.append(start)
24 flag=False
25 for i in self.lst[start]:
26 if i==end:
27 q.append(i)
28 return True,q
29 if self.checklist[i]:
30 pass
31 else:
32 flag=True
33 self.checklist[i]=True
34 q.append(i)
35 break
36 if flag:
37 store,extra=self.explore(q[-1],end)
38 if store==False:
39 q.pop()
40 if len(q)==0:return False
41 return self.explore(q[-1],end)
42 elif store==None:
43 pass
44 elif store==True:
45 q.pop()
46 q.extend(extra)
47 return True,q
48 else:
49 return False,None
50 def __str__(self):return str(self.lst)
51if __name__=='__main__':
52 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]}
53 a=Graph(store)
54 a.find_path(1,11) # No Path Found
55 a.find_path(1,6)# [1, 4, 5, 6]
56 a.find_path(3,10) # [3, 2, 1, 4, 5, 6, 9, 10]
57 a.find_path(4,10)# [4, 5, 6, 9, 10]
58 print(a) #
1# left to right, pre-order depth first tree search, recursive. O(n) time/space
2def depthFirstSearchRec(root):
3 if root == None: return
4 print(root)
5 depthFirstSearch(root.left)
6 depthFirstSearch(root.right)