Breadth-first search (BFS) Using Python

Breadth-first search (BFS) is a graph traversal algorithm that starts at the root node and explores all the nodes at the current depth level before moving on to the nodes at the next depth level. It uses a queue to store the nodes that need to be explored, and processes the nodes in the order they were added to the queue. BFS is commonly used to find the shortest path between two nodes in an unweighted graph.

Here is the code for a function that performs BFS on a graph represented as an adjacency list in Python:

from collections import deque

def bfs(graph, start):
  # Initialize the queue with the start node
  queue = deque([start])
  # Initialize a set to store the visited nodes
  visited = set()
  
  # Iterate over the queue until it is empty
  while queue:
    # Get the next node from the queue
    node = queue.popleft()
    # If the node has not been visited, visit it and add it to the visited set
    if node not in visited:
      visited.add(node)
      # Add the neighbors of the node to the queue
      queue.extend(graph[node])
  
  # Return the set of visited nodes
  return visited

# Test the function with a sample graph
graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
}
start = 'A'
print(bfs(graph, start))  # Output: {'A', 'B', 'C', 'D', 'E', 'F'}

This implementation of BFS has a time complexity of O(V+E), where V is the number of nodes and E is the number of edges in the graph. It is a simple and efficient algorithm for traversing the nodes of a graph, but it may not always find the shortest path between two nodes if the graph is weighted.