Thank you for printing our content at [Link].
Please check back soon for new
contents.
Learn to code efficiently ([Link]
36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]
Breadth first search
Traversal means visiting all the nodes of a graph. Breadth
First Traversal or Breadth First Search is a recursive
algorithm for searching all the vertices of a graph or tree
data structure.
BFS algorithm
A standard BFS implementation puts each vertex of the
graph into one of two categories:
1. Visited
2. Not Visited
The purpose of the algorithm is to mark each vertex as
visited while avoiding cycles.
The algorithm works as follows:
1. Start by putting any one of the graph's vertices at the
back of a queue.
2. Take
Thank you for printing ourthe frontatitem
content of the queue and add
[Link]. it tocheck
Please the back soon for new
contents.
visited list.
Learn to code efficiently ([Link]
36% 3. Create
with DSA Learn with
a list of that vertex's adjacent nodes. Add the
utm_source=sticky-
off
ones which aren't in
Programiz PRO the visited list to the back of the
banner&utm_campaign=programiz&utm_medium=referral)
([Link]
queue.
Programiz
utm_source=nav-
Search tutorials & examples
PRO (/)
floating&utm_campaign=programiz&utm_medium=referral)
4. Keep [Link]
steps 2 and 3 until the queue is empty.
The graph might have two different disconnected parts
so to make sure that we cover every vertex, we can also
run the BFS algorithm on every node
BFS example
Let's see how the Breadth First Search algorithm works
with an example. We use an undirected graph with 5
vertices.
Undirected graph with 5 vertices
We start from vertex 0, the BFS algorithm starts by putting
it in the Visited list and putting all its adjacent vertices in
the queue.
Thank you for printing our content at [Link]. Please check back soon for new
contents.
Learn to code efficiently ([Link]
36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]
Visit start vertex and add its adjacent vertices to queue
Next, we visit the element at the front of queue i.e. 1 and
go to its adjacent nodes. Since 0 has already been visited,
we visit 2 instead.
Visit the first neighbour of start node 0, which is 1
Vertex
Thank you for printing 2 has
our an unvisited
content adjacent vertexPlease
at [Link]. in 4, so we add
check back soon for new
contents.
that to the back of the queue and visit 3, which is at the
Learn tofront of the queue.
code efficiently ([Link]
36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]
Visit 2 which was added to queue earlier to add its neighbours
4 remains in the queue
Only 4 remains in the queue since the only adjacent node
of 3 i.e. 0 is already visited. We visit it.
Visit last remaining item in the queue to check if it has unvisited
neighbors
Sinceour
Thank you for printing thecontent
queue atis [Link].
empty, we have completed
Pleasethe Breadth
check back soon for new
contents. First Traversal of the graph.
Learn to code efficiently ([Link]
36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
utm_source=nav-
Search tutorials & examples
PRO BFS pseudocode
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]
create a queue Q
mark v as visited and put v into Q
while Q is non-empty
remove the head u of Q
mark and enqueue all (unvisited) neighbours of u
Python, Java and C/C++ Examples
The code for the Breadth First Search Algorithm with an
example is shown below. The code has been simplified so
that we can focus on the algorithm rather than other
details.
Python Java C C++
# BFS algorithm in Python
Thank you for printing our content at [Link]. Please check back soon for new
contents.
import
Learn to code collections ([Link]
efficiently
36%
off
with DSA Learn with utm_source=sticky-
# BFS algorithm
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
def([Link]
bfs(graph, root):
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/) visited, queue = set(), [Link]([root])
floating&utm_campaign=programiz&utm_medium=referral)
[Link]
[Link](root)
while queue:
# Dequeue a vertex from queue
vertex = [Link]()
print(str(vertex) + " ", end="")
# If not visited, mark it as visited, and
# enqueue it
for neighbour in graph[vertex]:
if neighbour not in visited:
[Link](neighbour)
[Link](neighbour)
if __name__ == '__main__':
graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
print("Following is Breadth First Traversal: ")
bfs(graph, 0)
BFS Algorithm Complexity
The time complexity of the BFS algorithm is represented in
the form of O(V + E) , where V is the number of nodes
and E is the number of edges.
The space complexity of the algorithm is O(V) .
BFS Algorithm Applications
1. To build index by search index
2. For GPS navigation
3. Path
Thank you for printing ourfinding
contentalgorithms
at [Link]. Please check back soon for new
contents.
4. In Ford-Fulkerson algorithm to find maximum flow in a
Learn to code efficiently ([Link]
36% network
with DSA Learn with utm_source=sticky-
off
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
5. Cycle detection in an undirected graph
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
6. In(/)floating&utm_campaign=programiz&utm_medium=referral)
minimum spanning tree (/dsa/spanning-tree-and-
[Link]
minimum-spanning-tree)
Next Tutorial:
Bellman Ford's (/dsa/bellman-ford-
algorithm)
Algorithm
Previous Tutorial:
(/dsa/graph-dfs)
DFS Algorithm
Share on:
([Link] ([Link]
u=[Link] text=Check%20this%2
bfs)
Did you find this article helpful?
Thank you for printing our content at [Link]. Please check back soon for new
contents.
Learn to code efficiently ([Link]
36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]
Our premium learning platform, created with
over a decade of experience.
Try Programiz PRO
([Link]
utm_source=tutorial-
banner-
bottom&utm_campaign=programiz&utm_medium=referral)
Related Tutorials
DS & Algorithms
Depth First Search (DFS)
(/dsa/graph-dfs)
DS & Algorithms
Adjacency List
(/dsa/graph-adjacency-list)
DS & Algorithms
Strongly Connected Components
(/dsa/strongly-connected-components)
DS & Algorithms
Ford-Fulkerson
Thank you for printing our contentAlgorithm
at [Link]. Please check back soon for new
contents.
([Link]
Learn to(/dsa/ford-fulkerson-algorithm)
code efficiently
36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]