Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Depth First Search Python Implementation : Prints all the nodes of the graph
def depth_first_search(graph, start_node):
visited_neighbours = set() #Keep track of the node we have visited like breadcrumbs to know the path
neighbours = [start_node] #list to store the neighbors. We will start with neigbors of void, the start node
while (len(neighbours) != 0): #All the elements will be transversed by the time we have this list size as zero
neighbour = neighbours.pop() #pop will take out randomly any one element and deletes from the list
if neighbour not in visited_neighbours:
visited_neighbours.add(neighbour)
new_prospected_neighbours = graph[neighbour]
#Need to remove neighbours which are already visted
new_neighbours = new_prospected_neighbours - visited_neighbours
neighbours.extend(new_neighbours)
return visited_neighbours
depth_first_search(graph, 'A')
#output: {'A', 'B', 'C', 'D', 'E', 'F', 'G'}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment