Breadth-first search (BFS) is an algorithm used to traverse or search through graphs and tree data structures. It explores all the nodes at a given depth level before moving on to the next level. This differs from depth-first search which visits nodes down a particular branch as far as possible before backtracking.
BFS has some key qualities that make it useful in a variety of applications:
- Explores nodes in increasing order of distance from starting node
- Can calculate shortest path distances on unweighted graphs
- Detects bipartite graphs and cycles in graphs
- Great for exploring network connectivity and relationships
Connected Devices Growth Driving Graph Algorithms
Industry research predicts over 125 billion connected IoT devices deployed by 2030, a 3x increase from 2020 levels [1]. As modern products from watches to appliances become networked, breadth-first search allows efficiently analyzing their connectivity.
How the BFS Algorithm Works
The breadth-first search algorithm uses a queue to keep track of the nodes to visit next. Here is some pseudo code showing how it operates:
BFS(graph, start):
queue = [start]
visited = [start]
while queue is not empty:
current = queue.pop()
visit(current)
for neighbor in graph.neighbors(current):
if neighbor not in visited:
visited.add(neighbor)
queue.add(neighbor)We initialize a queue data structure with the starting node and mark it visited. Then in a loop, we remove the next node to visit from the front of the queue (pop operation) and process that node. For each of its neighbors, we check if they have already been visited – if not, we mark them visited and add them to the back of the queue to be visited later.
This allows us to traverse all reachable nodes from the starting point by exploring the graph outwards level-by-level. Next we‘ll walk through an example in more depth.
Iterative vs. Recursive Implementations
The above shows an iterative approach, but BFS can also be implemented recursively. The recursive form can incur larger memory costs due to multiple active function calls, but enables parallel processing across subtrees [2]. Modern BFS variations optimize for GPU hardware by strategically managing recursion depth [3].
Breadth-First Search Example and Code
Let‘s look at how BFS would traverse this sample graph:
[insert graph visualization]And here is some Python code showing an implementation of BFS on this graph:
from collections import defaultdict, deque
import threading
# Function for performing BFS
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
current = queue.popleft() # Get next node
# Process node in separate thread
thread = threading.Thread(
target=process_node, args=(current))
thread.start()
visited.add(current)
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor) # Add to end of queue
# Create graph
graph = defaultdict(list)
edges = [("A","B"),("A","C"),("B","D")]
for edge in edges:
graph[edge[0]].append(edge[1])
bfs(graph, "A") # Call bfs starting at node AWalking through the key aspects:
- Use defaultdict to create graph
- Edges list defines connections
- Add edges in both directions
- bfs function accepts graph and start node
- Use set to track visited, queue for nodes to visit
- Process each node in a separate thread to allow parallelism across CPU cores
- Loop through neighbors and add unvisited ones to queue
Researchers have developed optimizations to make parallel BFS more bandwidth and cache efficient on multi-core systems [4].
Modifications for Disconnected Graphs
The previous BFS algorithm works well for connected graphs. However, sometimes a graph can consist of components that are disconnected from one another. In these cases, we need to add another loop to find the unvisited nodes and restart the search.
Here is updated pseudo code:
BFS(graph):
for each node in graph:
if node is not visited:
BFS(graph, node) # Call BFS on componentAnd in Python:
def bfs_disconnected(graph):
visited = set()
for node in graph:
if node not in visited:
bfs(graph, node)
visited.add(node)So we simply check if a node has been visited already whenever we start BFS on a new component. This allows us to perform breadth-first search even when parts of the graph are not connected.
Analyzing Time and Space Complexity
Now let‘s analyze the algorithm‘s computational performance.
Time Complexity
| Case | Complexity |
|---|---|
| Best | O(V+E) |
| Average | O(V+E) |
| Worst | O(V+E) |
- V – number of vertices (nodes)
- E – number of edges
We can see the time complexity is the same in all cases. BFS needs to potentially explore all reachable vertices and edges so performance depends on the size of the full graph.
Space Complexity
| Case | Complexity |
|---|---|
| Best | O(V) |
| Average | O(V) |
| Worst | O(V) |
Just like time, the space required is output only dependent on V, the number vertices. We need to store each node in the visited set as they are encountered.
So in summary, performance scales linearly with the number of nodes and edges in the graph. The structure of the graph does not impact complexity.
Optimization Research
Academic papers have developed advanced techniques to optimize BFS on GPU hardware, reducing memory footprint and enhancing parallelism. These leverage the fact that graphs often have predictable structure and connectivity [5].
Applications of Breadth-First Search
With an understanding of how it operates, let‘s explore some of the use cases where breadth-first shines.
Shortest Path Calculations
On unweighted graphs, BFS can calculate minimum path lengths between nodes. The first time we encounter a node yields the shortest path from the start.
Bipartite Graph Detection
A bipartite graph consists of two disjoint sets where connections only exist between the two sets, not within them. The level-by-level searching of BFS makes it well-suited for identifying whether a graph has this quality.
Cycle Detection
If while exploring we end up visiting the same node twice, we know there must be a cycle in the graph structure. BFS makes it easy to detect cycles.
Network Exploration
BFS naturally spreads outwards exploring network connectivity layer-by-layer. It serves as a great choice for understanding relationships and traversal potentials.
Web Crawling
Search engines leverage BFS to crawl the web graph, indexing pages level-by-level to quickly reach the majority of content [6].
Social Network Analysis
BFS can calculate node centrality metrics indicating most well-connected people. Social networks often have small-world structure well-suited for breadth-first algorithms [7].
Comparison to Other Graph Algorithms
There are a couple other common graph algorithms that have some similarities and differences from breadth-first search:
Depth-First Search
While BFS explores nodes level-by-level, DFS goes deep down a branch before backtracking. DFS uses a stack, BFS uses a queue. DFS processes less nodes but can get stuck in infinite loops, BFS sees all reachable nodes.
Dijkstra‘s Algorithm
Dijkstra‘s can also calculate shortest paths, but it works on weighted graphs. It uses priority queues to visit closer nodes first. BFS assumes uniform weights.
So in summary, BFS trades off some speed for safer exploration on unweighted graph types. The level-by-level approach also lends itself to certain graph properties.
What is the time complexity of BFS?
The time complexity is O(|V| + |E|) where |V| is number of vertices and |E| is number of edges. It depends on the size of the graph.
What is Breadth-First Search?
BFS is an algorithm for exploring or searching through graph data structures by visiting neighboring nodes first before moving on to the next level. This contrasts depth-first search which goes down a branch completely before backtracking.
How does it work?
It uses a queue to keep track of the nodes to visit next. We enqueue neighbors of the current node if they have not already been visited. This continues until all reachable nodes have been seen.
What data structures does it use?
The main data structures are a set or hash table to track visited nodes, preventing repeat visits, and a queue (typically FIFO) to manage nodes left to explore.
How does the performance scale?
The time and space complexity depend on the number of vertices (V) and edges (E) in the graph. So performance scales linearly as the graph gets larger.
How is BFS different from DFS and Dijkstra‘s?
DFS visits nodes along a branch deeply before backtracking while BFS explores the graph outwards level-by-level. Dijkstra‘s handles weighted graphs and uses priority queues while BFS assumes uniform weights.
