depth first search
# 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'))