concept · INFO-CS-ADS-103Breadth-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 Traversal
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.
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
| Name | Description |
|---|
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
| Question | Answer |
|---|
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