Breadth-First Search
- In Turkish
- Genişlik Öncelikli Arama
- Pronunciation
- BREDTH-furst surch
In short
Breadth-first search is a graph traversal algorithm that visits nodes in order of their distance from the start, exploring all neighbors before going deeper.
What is breadth-first search?
Breadth-first search (BFS) is an algorithm for exploring a graph or tree level by level. It starts at one node, visits all of that node's direct neighbors, then all of their neighbors, and so on, moving outward in rings. As a result, it reaches every node in order of how many edges away from the start it is.
BFS keeps a queue of nodes waiting to be explored, which is what makes it expand outward evenly. It removes the node at the front of the queue, adds each neighbor it hasn't seen before to the back, and marks those neighbors as visited so that cycles can't make it loop forever. With an adjacency list, BFS processes every reachable vertex and edge once, so it runs in O(V + E) time, where V is the number of vertices and E the number of edges, and it needs O(V) extra memory for the queue and the visited set.
Picture ripples spreading from a stone dropped in a pond: the ring closest to the center forms first, then the next one, and so on. Because of this, BFS finds the shortest path by number of edges in an unweighted graph, such as the fewest moves to solve a puzzle, the fewest hops between two network devices, or the degrees of separation between two people in a social network. Web crawlers and level-order traversal of trees also use BFS.
BFS is most often compared with depth-first search (DFS). DFS uses a stack, or recursion, to follow one path as deep as it can before backtracking, while BFS uses a queue to explore the nearest nodes first; both take O(V + E) time. BFS only guarantees shortest paths when every edge has the same cost, so weighted graphs need Dijkstra's algorithm instead, and on very wide graphs BFS can use a lot of memory, because an entire level may sit in the queue at once.
Key takeaways
- BFS explores a graph level by level, visiting the closest nodes first.
- It uses a queue, plus a visited set so that no node is processed twice.
- It runs in O(V + E) time with an adjacency list and uses O(V) extra memory.
- BFS finds the shortest path by number of edges in an unweighted graph.
- BFS goes wide using a queue; DFS goes deep using a stack.
Example
from collections import deque
def bfs_distances(graph, start):
distance = {start: 0} # also serves as the visited set
queue = deque([start])
while queue:
node = queue.popleft() # O(1): take the oldest, closest node first
for neighbor in graph[node]:
if neighbor not in distance: # skip nodes already seen
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return distance
friends = {"ana": ["ben", "cy"], "ben": ["dee"], "cy": ["dee"], "dee": ["eve"], "eve": []}
print(bfs_distances(friends, "ana")) # {'ana': 0, 'ben': 1, 'cy': 1, 'dee': 2, 'eve': 3}Readers ask
What is the difference between BFS and DFS?
BFS explores all nodes at the current distance before moving farther away, using a queue. DFS follows one path as deep as possible before backtracking, using a stack or recursion. Both run in O(V + E) time, but only BFS finds shortest paths by edge count.
Does BFS always find the shortest path?
It finds the path with the fewest edges, which is the shortest path when all edges have the same cost. When edges have different weights, such as road distances, use Dijkstra's algorithm instead.
What is the time complexity of breadth-first search?
With an adjacency list, BFS runs in O(V + E) time, because it processes each vertex and each edge a constant number of times. With an adjacency matrix, it takes O(V^2), since finding each node's neighbors means scanning a whole row.
Often compared
See also
- GraphData Structures, p. 15A graph is a data structure made of nodes, called vertices, connected by edges, and is used to model relationships such as roads, friendships, and dependencies.
- QueueData Structures, p. 26A queue is a data structure that stores items in first in, first out (FIFO) order, so the item that has waited longest is always the next one removed.
- Depth-First SearchData Structures, p. 10Depth-first search is a graph traversal algorithm that follows one path as far as it can go before backtracking to explore the next unvisited branch.
- TreeData Structures, p. 33A tree is a hierarchical data structure made of nodes connected by edges, with a single root node at the top and child nodes branching out below it.
- Big O NotationProgramming Fundamentals, p. 6Big O notation describes how an algorithm's running time or memory use grows as its input gets larger, focusing on the growth rate rather than exact speed.
- AlgorithmProgramming Fundamentals, p. 2An algorithm is a finite, step-by-step set of instructions for solving a problem or completing a task, such as sorting a list or finding the shortest route.
Spotted a mistake or something missing on this page?Suggest an edit