✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-103

Breadth-First Search (BFS)

Breadth-First Search is a graph traversal algorithm that explores vertices in increasing order of their distance from a starting vertex. It uses a queue and is commonly used for unweighted shortest-path problems and connectivity analysis.

Explanation

Overview

Breadth-First Search (BFS) is a traversal algorithm that visits a starting vertex, explores all its immediate neighbors, and then continues with vertices at progressively greater distances.

Key concepts

name: Core idea; description: The central focus of breadth-first search (bfs) is the capability described here: Breadth-First Search is a graph traversal algorithm that explores vertices in increasing order of their distance from a starting vertex. It uses a queue and is commonly used for unweighted shortest-path problems and connectivity analysis.; name: Problem context; description: Breadth-First Search (BFS) is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using breadth-first search (bfs), check its assumptions, input requirements, expected output, and resource constraints.

Time complexity

adjacencyList: O(V + E); adjacencyMatrix: O(V²)

Space complexity

O(V) for the queue, visited information, and optional parent and distance structures, excluding graph storage.

Pseudocode

BFS(G, start): mark start visited; enqueue(start); while queue is not empty: u = dequeue(); for each neighbor v of u: if v is not visited: mark v visited; parent[v] = u; enqueue(v).

Applications

Finding shortest paths in unweighted graphs; Finding connected components in undirected graphs; Checking graph connectivity; Level-order traversal of trees; Finding minimum-hop routes in networks; Exploring states in unweighted state-space problems

Advantages

Finds minimum-edge paths in unweighted graphs.; Systematically explores nearby vertices first.; Works with both directed and undirected graphs.; Has linear time complexity with adjacency lists.

Example or application

A worked example has not yet been added.

Definition

Breadth-First Search (BFS) is a traversal algorithm that visits a starting vertex, explores all its immediate neighbors, and then continues with vertices at progressively greater distances.

Core Principle

Explore the graph level by level.

Data Structure

Queue (FIFO)

Visited Tracking

A visited set or boolean array prevents repeatedly processing vertices and handles cycles safely.

Algorithm Steps

  • Choose a starting vertex.

  • Mark the starting vertex as visited.

  • Insert the starting vertex into a queue.

  • Remove the front vertex from the queue.

  • Examine all its unvisited neighbors.

  • Mark each newly discovered neighbor as visited and enqueue it.

  • Repeat until the queue becomes empty.

Pseudocode

BFS(G, start): mark start visited; enqueue(start); while queue is not empty: u = dequeue(); for each neighbor v of u: if v is not visited: mark v visited; parent[v] = u; enqueue(v).

Example Graph

A

  • B

  • C

B

  • D

  • E

C

  • F

D

No items supplied.

E

No items supplied.

F

No items supplied.

Example Traversal

Start Vertex

A

Possible Order

  • A

  • B

  • C

  • D

  • E

  • F

Note

Traversal order among vertices at the same level depends on neighbor ordering.

Distance Levels

BFS assigns the starting vertex distance zero and discovers other vertices in nondecreasing order of the number of edges from the start.

Shortest Path Property

In an unweighted graph, BFS finds shortest paths measured by the number of edges from the starting vertex to every reachable vertex.

Parent Tracking

A parent array or map can record how each vertex was first discovered, allowing a shortest path to be reconstructed.

Time Complexity

Adjacency List

O(V + E)

Adjacency Matrix

O(V²)

Space Complexity

O(V) for the queue, visited information, and optional parent and distance structures, excluding graph storage.

Applications

  • Finding shortest paths in unweighted graphs

  • Finding connected components in undirected graphs

  • Checking graph connectivity

  • Level-order traversal of trees

  • Finding minimum-hop routes in networks

  • Exploring states in unweighted state-space problems

Advantages

  • Finds minimum-edge paths in unweighted graphs.

  • Systematically explores nearby vertices first.

  • Works with both directed and undirected graphs.

  • Has linear time complexity with adjacency lists.

Limitations

  • May require substantial memory for wide graphs.

  • Does not directly solve general weighted shortest-path problems.

  • Only reaches vertices accessible from the chosen starting vertex.

  • Requires visited tracking to avoid repeated exploration.

Important Considerations

  • Mark vertices visited when they are enqueued, not when they are removed, to avoid duplicate queue entries.

  • For disconnected graphs, run BFS from additional unvisited vertices to traverse every component.

  • For weighted graphs with equal edge weights, BFS can still determine minimum-edge paths.

  • Neighbor ordering can change traversal order without changing BFS distance results.

Related Concepts

  • Queues

  • Depth-First Search

  • Shortest Path Problems

  • Graph Connectivity

  • Level-Order Traversal

Key Concepts

NameDescription

Core idea

The central focus of breadth-first search (bfs) is the capability described here: Breadth-First Search is a graph traversal algorithm that explores vertices in increasing order of their distance from a starting vertex. It uses a queue and is commonly used for unweighted shortest-path problems and connectivity analysis.

Problem context

Breadth-First Search (BFS) is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using breadth-first search (bfs), check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of breadth-first search (bfs)?

Breadth-First Search is a graph traversal algorithm that explores vertices in increasing order of their distance from a starting vertex. It uses a queue and is commonly used for unweighted shortest-path problems and connectivity analysis.

What should be checked before applying breadth-first search (bfs)?

For breadth-first search (bfs), verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of breadth-first search (bfs) be validated?

Trace a representative breadth-first search (bfs) case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of breadth-first search (bfs).

  • Identify the assumptions, inputs, and conditions relevant to breadth-first search (bfs).

  • Evaluate an application of breadth-first search (bfs) for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures