Dfs Python

Source URL: https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python

Language: python

Created on: 2020-10-05 20:21:31

###############
#The Algorithm (In English):

# 1) Pick any node. 
# 2) If it is unvisited, mark it as visited and recur on all its 
#    adjacent nodes. 
# 3) Repeat until all the nodes are visited, or the node to be 
#    searched is found.


# The graph below (declared as a Python dictionary)
# is from the linked website and is used for the sake of
# testing the algorithm. Obviously, you will have your own
# graph to iterate through.
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

visited = set() # Set to keep track of visited nodes.


##################
# The Algorithm (In Code)

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)
            
# Driver Code to test in python yourself.
# Note that when calling this, you need to
# call the starting node. In this case it is 'A'.
dfs(visited, graph, 'A')

# NOTE: There are a few ways to do DFS, depending on what your
# variables are and/or what you want returned. This specific
# example is the most fleshed-out, yet still understandable,
# explanation I could find.
How to implement depth-first search in Python
content_copy