2. Breadth-First Search

Introduction

Breadth-First Search (BFS) is a graph traversal algorithm used to explore or search through a graph in a breadthward motion. It starts at a given vertex and explores all its neighbors before moving on to the next level of vertices. It has various applications. For example, it can be used to determining connectivity in a graph or to find the shortest path between two vertices.

Algorithm

The BFS algorithm can be implemented using a queue. Here is a basic outline of the algorithm:

1. Choose a starting vertex and enqueue it.
2. While the queue is not empty, dequeue a vertex and mark it as visited.
3. Enqueue all the unvisited neighbors of the dequeued vertex.
4. Repeat steps 2 to 3 until the queue is empty.

Exercise

1. Run BFS algorithm starting at vertex 0 with Auto Play.
2. Change the starting vertex to 3 and run the algorithm manually (by clicking First Step).
3. Try to make a graph with 5 vertices and any number of edges. Choose a starting vertex and calculate the traversal order using BFS without looking at the result. Then, run the algorithm to check your answer.

BFS using a Queue

In the queue-based implementation of BFS, we start with the initial node and enqueue it. Then, while the queue is not empty, we dequeue a node from the front of the queue, visit it, and enqueue its unvisited neighboring nodes at the current depth level. This ensures that we visit all the nodes at the current level before moving on to the nodes at the next level.

from collections import deque  # Use it as a queue data structure

def traversal(adjacency_list):
    visited = set()  # Keep track of visited nodes

    def bfs_queue(start):
        queue = deque([start])  # Use a queue to keep track of the nodes to visit next

        while queue:
            current = queue.popleft()  # Take out the current node from the queue
            visited.add(current)
            print(current)  # Print the visited node

            # Add unvisited neighboring nodes into the queue
            for neighbor in adjacency_list[current]:
                if neighbor not in visited:
                    queue.append(neighbor)

    # Iterate through all nodes in the graph
    for vertex in adjacency_list:
        if vertex not in visited:
            bfs_queue(vertex)

function traversal(adjacencyList) {
  const visited = new Set() // Keep track of visited nodes

  function bfsQueue(start) {
    const queue = [] // Use an array as a queue to keep track of the nodes to visit next
    queue.push(start)

    while (queue.length > 0) {
      const current = queue.shift() // Take out the current node from the queue
      visited.add(current)
      console.log(current) // Print the visited node

      // Add unvisited neighboring nodes into the queue
      for (let neighbor of adjacencyList[current]) {
        if (visited.has(neighbor)) continue
        queue.push(neighbor)
      }
    }
  }

  // Iterate through all nodes in the graph
  for (let vertex in adjacencyList) {
    if (visited.has(vertex)) continue
    bfsQueue(vertex)
  }
}