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 vote327 views1 answer
How to count number of records in json
Python
0 vote313 views1 answer
Pandas df represent a long column name with short name
Python
0 vote373 views1 answer
Entry point to programming Spark with the Dataset and DataFrame API
Python
0 vote332 views1 answer
Perform a right outer join of self and other.
Python
1 vote341 views2 answers
Git help
Python
0 vote317 views1 answer
Roganrola
Python
2 votes347 views1 answer
No module named social_django
Python
0 vote364 views2 answers
Selenium check if driver is open python
Python
0 vote381 views1 answer
Python how to get current line number
Python
1 vote317 views2 answers
Pedagogical example
Python