Breadth first search (BFS) is one of the easiest algorithms for searching a graph. It also serves as a prototype for several other important graph algorithms that we will study later.
It uses the opposite strategy of depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.
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.
-
Pick any node, visit the adjacent unvisited vertex, mark it as visited, display it, and insert it in a queue.
-
If there are no remaining adjacent vertices left, remove the first vertex from the queue.
-
Repeat step 1 and step 2 until the queue is empty or the desired node is found.
Since all of the nodes and vertices are visited, the time complexity for BFS on a graph is:
O(V+E);
- V = Number of Vertices.
- E = Number of edges.
Simple demo:
GRAPH ={
'a': ['b', 'c'],
'b': ['d', 'e'],
'c': ['f'],
'd': [],
'e': ['f'],
'f': []
}
def bfs(graph, source):
visited = [source]
queue = [source]
while queue:
s = queue.pop(0)
for neighbour in graph[s]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
return [n.upper() for n in visited]
tree = bfs(GRAPH, 'a')
print(tree)
# ['A', 'B', 'C', 'D', 'E', 'F']
Trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This search is referred to as breadth-first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.
-
Depth-first search Breadth-first search Iterative deepening depth-first search Monte Carlo tree search
-
Copying garbage collection
-
Finding the shortest path between two nodes u and v, with path length measured by number of edges (an advantage over depth-first search)
-
Ford–Fulkerson method for computing the maximum flow in a flow network
-
Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
-
Construction of the failure function of the Aho-Corasick pattern matcher.
-
Testing bipartiteness of a graph
PSEUDOCODE
procedure BFS(G, v) is
create a queue Q
enqueue v onto Q
mark v
while Q is not empty do
w ← Q.dequeue()
if w is what we are looking for then
return w
for all edges e in G.adjacentEdges(w) do
x ← G.adjacentVertex(w, e)
if x is not marked then
mark x
enqueue x onto Q
return null
-
queue (First In First Out
-
adjacency list | adjacency matrix
-
BFS ordering
In a Breadth First search if you instead of a Queue you use a Priority Queue and define a sorting function on the nodes such that the node with the lowest cost is at the top of the Priority Queue you basically are doing a Dijkstra (Heap method)
This allows us to find the best path through a graph in O(m * log(n)) time where n is the number of vertices and m is the number of edges in the graph.