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

0 vote318 views1 answer
Fetch firestore indexes
Python
54 votes292 views3 answers
Python add up values in list
Python
0 vote301 views1 answer
Pythonpath manager spyder
Python
12 votes282 views2 answers
Python sorted function descending
Python
0 vote339 views1 answer
Aggregate the elements of each partition, and then the results for all the partitions
Python
0 vote294 views1 answer
Df = df.apply(lambda x: np.square(x) if x.name in [ 'a', 'e', 'g'] else x, axis=1)
Python
1 vote326 views1 answer
Fastest way to output text file in python + Cout
Python
41 votes282 views6 answers
Python print new line
Python
10 votes302 views4 answers
Check the role of user in on_message discord.py
Python
0 vote268 views1 answer
Python : a counter
Python