Breadth-First Search (BFS)

Definition

Definition

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the neighbor nodes at the present depth before moving on to the nodes at the next depth level. It operates on a data structure called a queue, enabling it to visit nodes in a level-by-level manner

Explanation

Breadth-First Search (BFS) begins from a chosen node, typically known as the root node, within a graph. It systematically explores all neighbor nodes at the current depth level before proceeding to nodes at deeper levels. Utilizing a queue, BFS manages the nodes awaiting exploration, initially adding the starting node to the queue. While the queue remains populated, BFS dequeues a node and examines its adjacent nodes. To prevent revisiting nodes and cycles, BFS marks each explored node as visited. This exploration process persists until the queue exhausts its contents

Guidance

• enqueue the starting node onto a queue
• mark the starting node as visited
• while the queue is not empty
  • dequeue a node from the queue
  • visit the dequeued node and process it as needed
  • enqueue all of its unvisited neighbors onto the queue
  • mark each visited neighbor as visited
• continue this process until the queue becomes empty

Tips

• utilize a data structure like a queue to maintain the order of nodes to be visited
• ensure efficient marking of visited nodes to avoid unnecessary revisits
• BFS is particularly useful for finding the shortest path in unweighted graphs
• it's ideal for finding connected components and checking if a graph is bipartite

Practice

Practice

BFS(graph, start_node):
  initialize an empty queue
  enqueue start_node onto the queue
  mark start_node as visited

  while queue is not empty:
    current_node = dequeue from queue
    process current_node

    for each neighbor_node of current_node:
      if neighbor_node is not visited:
        mark neighbor_node as visited
        enqueue neighbor_node onto queue

Solution

// Graph BFS
func BFS(graph [][]int, start int) {
    visited := make([]bool, len(graph))
    queue := []int{start}
    visited[start] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        fmt.Print(node, " ")

        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
}

// Binary Tree BFS
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func BFS(root *TreeNode) {
    if root == nil {
        return
    }
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        fmt.Print(node.Val, " ")

        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
}

import java.util.*;

// Graph BFS
class Graph {

  void BFS(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
      int node = queue.poll();
      System.out.print(node + " ");

      for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.add(neighbor);
        }
      }
    }
  }
}

// Binary Tree BFS
class BinaryTree {

  void BFS(TreeNode root) {
    if (root == null) {
      return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      System.out.print(node.val + " ");

      if (node.left != null) {
        queue.add(node.left);
      }
      if (node.right != null) {
        queue.add(node.right);
      }
    }
  }

  class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }
}

// Graph BFS
function BFS(graph, start) {
  const visited = new Array(graph.length).fill(false);
  const queue = [start];
  visited[start] = true;

  while (queue.length > 0) {
    const node = queue.shift();
    process.stdout.write(node + " ");

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
}

// Binary Tree BFS
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = this.right = null;
  }
}

function BFS(root) {
  if (!root) {
    return;
  }
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    process.stdout.write(node.val + " ");

    if (node.left) {
      queue.push(node.left);
    }
    if (node.right) {
      queue.push(node.right);
    }
  }
}

// Graph BFS
fun BFS(graph: List<List<Int>>, start: Int) {
    val visited = BooleanArray(graph.size)
    val queue = LinkedList<Int>()
    queue.add(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        print("$node ")

        for (neighbor in graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true
                queue.add(neighbor)
            }
        }
    }
}

// Binary Tree BFS
class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun BFS(root: TreeNode?) {
    if (root == null) return
    val queue = LinkedList<TreeNode>()
    queue.add(root)

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        print("${node.`val`} ")

        node.left?.let { queue.add(it) }
        node.right?.let { queue.add(it) }
    }
}

# Graph BFS
from collections import deque

def BFS(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])
    visited[start] = True

    while queue:
        node = queue.popleft()
        print(node, end=' ')

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

# Binary Tree BFS
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def BFS(root):
    if not root:
        return
    queue = deque([root])

    while queue:
        node = queue.popleft()
        print(node.val, end=' ')

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

// Graph BFS
use std::collections::VecDeque;

fn bfs(graph: &Vec<Vec<usize>>, start: usize) {
    let mut visited = vec![false; graph.len()];
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited[start] = true;

    while let Some(node) = queue.pop_front() {
        print!("{} ", node);

        for &neighbor in &graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }
}

// Binary Tree BFS
#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn bfs(root: Option<Box<TreeNode>>) {
    if let Some(mut node) = root {
        let mut queue = VecDeque::new();
        queue.push_back(&mut node);

        while let Some(cur) = queue.pop_front() {
            print!("{} ", cur.val);

            if let Some(left) = &mut cur.left {
                queue.push_back(left);
            }
            if let Some(right) = &mut cur.right {
                queue.push_back(right);
            }
        }
    }
}

// Graph BFS
function BFS(graph: number[][], start: number): void {
  const visited: boolean[] = new Array(graph.length).fill(false);
  const queue: number[] = [start];
  visited[start] = true;

  while (queue.length > 0) {
    const node: number = queue.shift()!;
    process.stdout.write(node + " ");

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
}

// Binary Tree BFS
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function BFS(root: TreeNode | null): void {
  if (!root) return;
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const node: TreeNode = queue.shift()!;
    process.stdout.write(node.val + " ");

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}