PY
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
#The type of uninforemed searches.Depth-first search always expands the deepest node in the current frontier of the search tree.The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search “backs up” to the next deepest node that still has unexplored successors.
from queue import LifoQueue
graph={
'S':['C','B','A'],
'A':['S','E','D'],
'B':['S','G'],
'C':['A','F'],
'D':['A','H'],
'E':['A','G'],
'F':['C','G'],
'G':['B'],
'H':['D']
}
def dfs(startingNode, destinationNode):
#for keeping track of what we have visited
visited={}
#will keep track of distance
distance={}
#parent nodes in graph
parent={}
dfs_traversal_output=[]
#dfs using LIFO queue
queue=LifoQueue()
Enter to Rename, Shift+Enter to Preview
OUTPUT
Run