Implement a depth-first search algorithm and breadth-first search algorithm, use an undirected graph, and develop a recursive algorithm for searching for all the vertices of a graph or a tree data structure.

Spread this useful information with your friends if you liked.

What is Depth-first search?
  • Depth-first search is a recursive algorithm used to traverse tree or graph data structure.
  • It is called depth-first search because it starts with root node and follows each path to its greatest depth before moving to next path.
  • It uses stack data structure i.e. LIFO(Last In First Out).
  • Time Complexity is O(V+E)
  •   where, V = Vertices,
          E = Edges
#graph is a dictionary data structure, each vertex consist of 
#list of adjacent node stored.
graph={'A':['b','c'],
       'B':['d','e'],
       'C':['f'],
       'D':[],
       'E':['f'],
       'F':[]}

#visited is a set which keeps track of visited node, 
#initially it is empty   
visited = set()

def dfs(visited, graph, node):
#checks if node is present in visited or not
    if node not in visited:
    #if not present then print it and add in visited
        print(node)
        visited.add(node)
        
        for neighbor in graph[node]:
            dfs(visited, graph, neighbor)
        #for each neighbour of current node,
        #dfs function is invoked
dfs(visited, graph, 'A')

Breadth First Search

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = []		 # List to keep track of visited nodes.
queue = []     		#Initialize a queue

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s, end = " ") 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

bfs(visited, graph, 'A')




Spread this useful information with your friends if you liked.

Leave a Comment

Your email address will not be published. Required fields are marked *