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

6 votes225 views3 answers
Login system in django
Python Django
-1 vote199 views1 answer
Python how to make a user input function
Python
1 vote210 views3 answers
Python is float function
Python
0 vote222 views1 answer
Tensorflow turn off gpu
Python
5 votes208 views4 answers
Shebang python
Python
27 votes221 views4 answers
Python get exception message
Python
0 vote218 views1 answer
Opencv set window size
Python
0 vote222 views1 answer
List Delete a Element
Python
0 vote228 views1 answer
Python append many items to a list
Python
0 vote239 views1 answer
Extract name organization using nltk
Python