Dfs algorithm python

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

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)

Similar codes

4 votes157 views3 answers
How to convert list into csv in python
Python
7 votes256 views3 answers
Match case in Python
Python
0 vote153 views1 answer
Pygame.K_KP_ENTER
Python
0 vote216 views2 answers
Messe graphen erstellen python
Python
0 vote158 views1 answer
Fix the debug_mode = false django
Python
6 votes149 views6 answers
Palindrome
Python
2 votes145 views2 answers
Python how to sum two lists
Python
9 votes206 views5 answers
Get dummies pandas
Python
1 vote163 views1 answer
Tkinter boilerplate
Python
1 vote143 views1 answer
Python magic windows error
Python