python depth first search
# left to right, pre-order depth first tree search, recursive. O(n) time/space
def depthFirstSearchRec(root):
if root == None: return
print(root)
depthFirstSearch(root.left)
depthFirstSearch(root.right)python depth first search
# left to right, pre-order depth first tree search, recursive. O(n) time/space
def depthFirstSearchRec(root):
if root == None: return
print(root)
depthFirstSearch(root.left)
depthFirstSearch(root.right)dfs algorithm
# Depth First Search: DFS Algorithm
# 1) Pick any node.
# 2) If it is unvisited, mark it as visited and recur on all its
# adjacent (neighbours) nodes.
# 3) Repeat until all the nodes are visited
graph= {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['F'],
'D' : [],
'E' : ['F'],
'F' : []
}
visited = set() # Set to keep track of visited nodes of graph.
def dfs(visited, graph, node): #function for dfs
if node not in visited:
'''
We start with A
Then B
Then D
Then E
Then F
Then C
A -> B -> D -> E -> F -> C
'''
print(node)
# added to visited to avoid visit the node twice
visited.add(node)
for neighbour in graph[node]:
'''
* Neighbour of A : B and C but first visit B
* Then neighbour of B : D and E but first visit D
* Then neighbour of D : doesn't have neighbour then backtrack to the neighbour
of the previous node (B) which is E
* Then neighbour of E : F
* Then neighbour of F : doesn't have neighbour then backtrack to the neighbour
of the previous node E but doesn't have other neighbour except F which is visited
So backtracking again to B and B also doesn't have nodes not visited
So backtracking again to A: C not visited YAY!
'''
dfs(visited, graph, neighbour)
print(dfs(visited, graph, 'A'))Copyright © 2021 Codeinu
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems resetting your password contact us
