Breadth-First Search (BFS)

 

Breadth-First Search (BFS)

Breadth-First Search (BFS) is one of the simplest and most important graph-search algorithms. BFS systematically explores all vertices that are reachable from a given source vertex s.

The main idea is to explore the graph level by level, starting from the source.

Basic idea

Suppose the source is s.

BFS first discovers:

  • s — distance 0
  • All neighbors of s — distance 1
  • All undiscovered neighbors of those vertices — distance 2
  • Then vertices at distance 3, and so on.

Thus, BFS can be viewed as a series of waves expanding outward from the source.

Distance 0:        s

Distance 1:      A   B   C

Distance 2:    D   E   F   G

Distance 3:      H   I

The distance of a vertex is the minimum number of edges required to reach it from the source.

Queue-Based Exploration

BFS uses a FIFO (First-In, First-Out) queue.

The queue contains the vertices that have been discovered but whose adjacency lists have not yet been completely explored.

BFS uses three colors:

  • WHITE – vertex has not yet been discovered.
  • GRAY – vertex has been discovered and is currently on the frontier.
  • BLACK – all its adjacent vertices have been examined.

The process is:

WHITE → GRAY → BLACK

For example:

Undiscovered
    |
  WHITE
    ↓
Discovered
    |
  GRAY
    ↓
All neighbors examined
    |
  BLACK

Breadth-First Tree

BFS also constructs a breadth-first tree rooted at the source vertex.

Whenever BFS discovers a new vertex v while examining vertex u, it records:

v.parent = u

and adds the edge (u,v) to the BFS tree.

For example:

          s
        /   \
       A     B
      / \     \
     C   D     E

The path from s to any reachable vertex in this BFS tree corresponds to a shortest path in the original graph, where the length is measured by the number of edges.

For example:

s → A → D

is a shortest path from s to D.

Important Properties of BFS

1. Finds all reachable vertices

BFS discovers every vertex that can be reached from the source.

Vertices that cannot be reached from s remain WHITE.

2. Computes shortest-path distances

For every reachable vertex v:

v.d

stores the minimum number of edges from s to v.

Thus:

s.d = 0

and if v is first discovered from u:

v.d = u.d + 1

3. Constructs a shortest-path tree

The predecessor attribute:

v.π

stores the parent of v in the BFS tree.

4. Uses a FIFO queue

The queue ensures that vertices are processed in increasing order of their distance from the source.

BFS Pseudocode


BFS Example





Summary

BFS explores a graph level by level from a source vertex using a FIFO queue, discovers every reachable vertex, computes its shortest distance from the source in terms of number of edges, and constructs a breadth-first tree representing shortest paths.

Comments

Post a Comment

Popular posts from this blog

Design and Analysis of Algorithms PCCST502 Semester 5 KTU CS 2024 Scheme - Dr Binu V P

About Me - Dr Binu V P Syllabus and Scheme Model Question Paper Design and Analysis of Algorithms PCCST502 KTU 2024 Scheme Module - I Introduction to Algorithms Criteria for Analyzing Algorithms - Time and Space Complexity Performance Analysis - Time and Space Complexity Asymptotic Analysis , Asymptotic Notations and their properties Comparing Growth Rates using Limits Standard Functions and notations Properties of Asymptotic Notations and common conjuctures Analyzing Algorithms - Insertion Sort ( Example ) Divide and Conquer Strategy using Merge Sort Divide and Conquer - Recurrences Analysis of Recursive Algorithms Iteration Method(Expansion Method) Substitution Method Example Problems - Substitution Method Recursion Tree Method Example Problems - Recursion Tree Method Master Method Example Problems-Master Method Akra-Bazzi Method Recurrences where the Master Theorem cannot be Applied Balanced Search Trees - AVL Trees Module - II Disjoint Sets Disjoint Sets (Union-Find Data Struc...
Read more

Introduction to Algorithms

  Introduction to Algorithms Algorithms form the foundation of Computer Science and software engineering. Every computational task—from searching the internet and processing transactions to artificial intelligence and scientific simulations—relies on algorithms. In the study of Algorithm Analysis and Design , understanding algorithms and their properties is essential before moving to advanced design techniques and complexity analysis. What is an Algorithm? An algorithm is a finite sequence of well-defined computational steps that transforms input into output to solve a particular problem. In simpler terms: An algorithm is a step-by-step procedure for solving a problem in a finite amount of time. An algorithm accepts some input , processes it through a sequence of instructions, and produces the required output . Formal Definition An algorithm can be viewed as: Algorithm = Input + Processing Steps + Output \text{Algorithm} = \text{Input} + \text{Processing Steps} + \...
Read more

Criteria for Analyzing Algorithms- Time and Space Complexity

  Criteria for Analyzing Algorithms Algorithm analysis is the process of evaluating an algorithm with respect to the resources it requires and its performance characteristics. The primary goal is to determine how efficiently an algorithm solves a problem as the size of the input increases. Different algorithms can solve the same problem, but their efficiencies may vary greatly. For example: One sorting algorithm may take seconds. Another may take hours for large datasets. Algorithm analysis helps us: Compare alternative algorithms Predict performance Select optimal solutions Understand scalability Estimate resource consumption Major Criteria for Analyzing Algorithms The important criteria used in algorithm analysis are: Time Complexity Space Complexity 1. Time Complexity Definition Time complexity measures the amount of computational time required by an algorithm as a function of input size. If input size is denoted by n n , then time complexity...
Read more