Mathematical Foundation of Breadth-First Search (BFS) Algorithm

Image courtesy Medium

Breadth-First Search (BFS) stands out for its simplicity in exploring graphs and trees. BFS is a fundamental algorithm for tasks ranging from finding the shortest path in unweighted graphs to network analysis. But what underpins this powerful algorithm? In this blog post, we’ll understand the math theory that forms the backbone of BFS.

1. Graph Theory Basics

To understand BFS, it's crucial to have a grasp of basic graph theory concepts:

• Graph: A graph G is defined as a pair (V,E) where V is a set of vertices (or nodes) and E is a set of edges (or links) connecting pairs of vertices.

• Undirected Graph: In an undirected graph, edges have no direction; the edge (u,v) is the same as (v,u).

• Directed Graph: In a directed graph, edges have direction; (u,v) is not the same as (v,u).

• Unweighted Graph: All edges have the same weight or no weight, which means the cost to traverse any edge is equal.

• Weighted Graph: Edges have different weights, which represent the cost or distance to traverse them.

  
  

2. BFS Algorithm Overview

Breadth-First Search explores a graph level by level from a given starting node. The core idea is to explore all nodes at the present depth before moving on to nodes at the next depth level. Here’s a high-level description of how BFS operates:

1. Initialization: Start at a chosen node (source). Mark it as visited and enqueue it.

2. Exploration: Dequeue a node from the front of the queue. Examine all its adjacent (or neighboring) nodes.

3. Enqueueing: If an adjacent node hasn’t been visited, mark it as visited and enqueue it.

4. Repeat: Continue the process until the queue is empty.

   
   

3. Mathematical Foundation of BFS

The mathematics behind BFS can be understood through several key concepts:

a. Queue Data Structure

• Properties: BFS uses a queue data structure to manage the nodes to be explored. A queue follows the First In, First Out (FIFO) principle, ensuring that nodes are processed in the order they were discovered.

• Mathematical Model: The queue can be represented as a list or array where elements are added to the end and removed from the front. Mathematically, if Q is a queue, the operations can be defined as:

  • Enqueue: Q.push(x) - Adds x to the end.

  • Dequeue: Q.pop() - Removes the front element.

b. Level-wise Exploration

• Level Definition: In BFS, nodes are explored level by level. Level l of a node is the number of edges on the shortest path from the source node.

• Mathematical Insight: Each node at level l is connected to nodes at level l+1 through a single edge. BFS ensures that nodes at the same level are processed before moving to nodes at the next level.

c. Shortest Path Property

• Unweighted Graphs: BFS guarantees that the shortest path from the source node to any other node is found in an unweighted graph. The distance from the source node to a node v is the minimum number of edges in the path from the source to v.

• Mathematical Proof: Consider a node u at level l and its neighbor v at level l+1. Since BFS processes nodes level by level, the shortest path from the source to v through u is guaranteed to be minimal. This is due to the fact that v is reached directly from uuu in the shortest possible manner.

d. Time Complexity

• Mathematical Analysis: The time complexity of BFS is O(V+E) where V is the number of vertices and E is the number of edges. This complexity arises because each vertex and edge is processed at most once during the traversal.

  • Vertex Processing: Each vertex is enqueued and dequeued exactly once.

  • Edge Processing: Each edge is examined once when its adjacent vertices are explored.

e. Space Complexity

• Mathematical Analysis: The space complexity of BFS is also O(V). This space is used to store the queue and the visited nodes.

  • Queue Storage: At most, the queue holds all nodes at a single level, which in the worst case could be O(V).

  • Visited Nodes: The visited nodes are tracked using an auxiliary array or set.

    
    

4. Example: BFS in Action

Let’s consider a simple graph example to illustrate BFS:

Graph: A - B - C |   | D - E

• Starting Node: A

• BFS Traversal:

  • Queue Initialization: [A]

  • Dequeue A: Explore neighbors B and D.

  • Queue Update: [B, D]

  • Dequeue B: Explore neighbors C and E.

  • Queue Update: [D, C, E]

  • Dequeue D: No new neighbors.

  • Queue Update: [C, E]

  • Dequeue C: No new neighbors.

  • Queue Update: [E]

  • Dequeue E: No new neighbors.

  • Queue Update: []

Final BFS Traversal Order: A, B, D, C, E.

5. Applications of BFS

BFS has a wide range of applications beyond finding shortest paths:

• Network Routing: Optimal routing in communication networks.

• Social Network Analysis: Finding shortest paths between users and detecting connected components.

• Puzzle Solving: Algorithms for solving puzzles like the 8-puzzle problem.

• Web Crawling: Efficiently exploring and indexing web pages.

  
  

Breadth-First Search's level-by-level exploration guarantees finding the shortest path in unweighted graphs and provides a good framework.

Feel free to dive deeper into BFS and experiment with the BFS visualizer above!