**Breadth-first search (BFS)** is an algorithm used for tree traversal on graphs or tree data structures. BFS can be easily implemented using recursion and data structures like dictionaries and lists.

## The Algorithm
1. Pick any node, visit the adjacent unvisited vertex, mark it as visited, display it, and insert it in a queue.
2.  If there are no remaining adjacent vertices left, remove the first vertex from the queue.
3. Repeat step 1 and step 2 until the queue is empty or the desired node is found.

## Implementation
Consider the​ graph, which ​is implemented in the code below:

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)

# Driver Code
bfs(visited, graph, 'A')

## Explanation
- **Lines 3-10**: The illustrated graph is represented using an *adjacency list*. An easy way to do this in Python is to use a *dictionary data structure*, where each vertex has a stored list of its adjacent nodes.

- **Line 12**: `visited` is a list that is used to keep track of visited nodes.
- **Line 13**: `queue` is a list that is used to keep track of nodes currently in the queue.
- **Line 29**: The arguments of the `bfs` function are the `visited` list, the `graph` in the form of a dictionary, and the starting node `A`.
- **Lines 15-26**: `bfs` follows the algorithm described above: 
  1. It checks and appends the starting node to the `visited` list and the `queue`.
  2. Then, while the queue contains elements, it keeps taking out nodes from the queue, appends the neighbors of that node to the queue if they are unvisited, and marks them as visited. 
  3. This continues until the queue is empty.

## Time Complexity
Since all of ​the nodes and vertices are visited, the time complexity for BFS on a graph is $O(V + E)$; where $V$ is the number of vertices and $E$ is the number of edges.

How to implement a ​breadth-first search in Python

The Algorithm

Implementation

Explanation

Time Complexity

How to implement a breadth-first search in Python