# 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'))

**Here is what the above code is Doing:**

1. We start with A

2. Then B

3. Then D

4. Then E

5. Then F

6. Then C

A -> B -> D -> E -> F -> C