BreadthFirst Search in all languages
BreadthFirst Search in Java
Posted: , Last Updated:
Java™ is a compiled language used for many purposes, ranging from embedded systems, UIapplications to web servers.
See CodeBreadthFirst Search in C
Posted: , Last Updated:
C is a compiled language used for many purposes, although it can be primarily found in systems where importance is important. This is because C offers a lot of lowlevel support for optimization, at the cost of not having some of the convenient abstractions that other languages offer. C is therefore primarily found in situations where available computation power is low such as embedded systems, or situations where required computation power is high, such as simulation or deep learning.
See CodeBreadthFirst Search in Javascript
Posted: , Last Updated:
JavaScript JavaScript is an interpreted scripting language previously primarily used in web pages (executed in browsers) that has since…
See CodeBreadthFirst Search in Python
Posted: , Last Updated:
Python Python™ is an interpreted language used for many purposes ranging from embedded programming to web development, with one of the largest use cases being data science.
See CodeBreadthFirst Search in R
Posted: , Last Updated:
R R is an interpreted language first released in 1993 with a significant increase in popularity in recent years. It is primarily used for data mining and science as well as statistics, and is a popular language in noncomputer science disciplines ranging from Biology to Physics. R is dynamically typed, and has one of the widest variety of libraries for statistics, machine learning, data mining etc.
See CodeAbout the algorithm:
BreadthFirst Search Algorithm
The Breadthfirst search algorithm is an algorithm used to solve the shortest path problem in a graph without edge weights (i.e. a graph where all nodes are the same “distance” from each other, and they are either connected or not). This means that given a number of nodes and the edges between them, the Breadthfirst search algorithm is finds the shortest path from the specified start node to all other nodes. Nodes are sometimes referred to as vertices (plural of vertex)  here, we’ll call them nodes.
Description of the Algorithm
The basic principle behind the Breadthfirst search algorithm is to take the current node (the start node in the beginning) and then add all of its neighbors that we haven’t visited yet to a queue. Continue this with the next node in the queue (in a queue that is the “oldest” node). Before we add a node to the queue, we set its distance to the distance of the current node plus 1 (since all edges are weighted equally), with the distance to the start node being 0. This is repeated until there are no more nodes in the queue (all nodes are visited).
In more detail, this leads to the following Steps:
 Initialize the distance to the starting node as 0. The distances to all other node do not need to be initialized since every node is visited exactly once.
 Set all nodes to “unvisited”
 Add the first node to the queue and label it visited.

While there are nodes in the queue:
 Take a node out of the queue
 For all nodes next to it that we haven’t visited yet, add them to the queue, set their distance to the distance to the current node plus 1, and set them as “visited”
In the end, the distances to all nodes will be correct.
Example of the Algorithm
Consider the following graph:
The steps the algorithm performs on this graph if given node 0 as a starting point, in order, are:
 Visiting node 0

Visited nodes: [true, false, false, false, false, false], Distances: [0, 0, 0, 0, 0, 0]
 Removing node 0 from the queue…
 Visiting node 1, setting its distance to 1 and adding it to the queue
 Visiting node 2, setting its distance to 1 and adding it to the queue

Visited nodes: [true, true, true, false, false, false], Distances: [0, 1, 1, 0, 0, 0]
 Removing node 1 from the queue…
 Visiting node 3, setting its distance to 2 and adding it to the queue
 Visiting node 4, setting its distance to 2 and adding it to the queue

Visited nodes: [true, true, true, true, true, false], Distances: [0, 1, 1, 2, 2, 0]
 Removing node 2 from the queue…
 No adjacent, unvisited nodes

Visited nodes: [true, true, true, true, true, false], Distances: [0, 1, 1, 2, 2, 0]
 Removing node 3 from the queue…
 Visiting node 5, setting its distance to 3 and adding it to the queue

Visited nodes: [true, true, true, true, true, true], Distances: [0, 1, 1, 2, 2, 3]
 Removing node 4 from the queue…
 No adjacent, unvisited nodes

Visited nodes: [true, true, true, true, true, true], Distances: [0, 1, 1, 2, 2, 3]
 Removing node 5 from the queue…
 No more nodes in the queue. Final distances: [0, 1, 1, 2, 2, 3]
Runtime Complexity of the Algorithm
The runtime complexity of Breadthfirst search is O(E + V) (V = number of Nodes, E = number of Edges) if adjacencylists are used. If a we simply search all nodes to find connected nodes in each step, and use a matrix to look up whether two nodes are adjacent, the runtime complexity increases to O(V^2).
Depending on the graph this might not matter, since the number of edges can be as big as V^2 if all nodes are connected with each other.
Space Complexity of the Algorithm
The space complexity of Breadthfirst search depends on how it is implemented as well and is equal to the runtime complexity.