Breadth First Search, or BFS, is a method used to explore all the nodes in a graph, step by step. It starts at one node (called the starting or source node) and checks all the nearby or connected nodes first. After visiting those, it moves on to check the neighbors of those nodes, and so on. This continues until there are no more nodes left to visit.

BFS uses a queue, a structure where the first item added is the first one taken out. This helps in making sure the nodes are visited in the right order — level by level.

BFS is very helpful when you want to find the shortest path between two points in an unweighted graph (where all edges are the same cost). It can also be used to check if a graph has any loops or cycles.

In this mathematics article, we will cover the various aspects of the Breadth First Search (BFS) algorithm such as its purpose, how it works, and its advantages. By the end of the article, the reader should have a clear idea of the underlying concepts and the mechanics of the BFS algorithm.

Breadth First Search

Breadth-First Search (BFS) is a method used to explore or search through a graph or a tree. It starts from a selected node, often called the starting or root node, and looks at all its nearby (adjacent) nodes first. After checking those, it moves on to explore the next level of nodes — the neighbors of the already visited ones — and continues this process level by level.

BFS uses a step-by-step approach, making sure it visits all nodes that are closer before moving on to those that are farther away. It uses a queue to keep track of which nodes to visit next and makes sure it doesn’t visit the same node more than once by keeping a list of visited nodes.

This method is widely used because it helps find the shortest path in unweighted graphs and is a good way to explore every part of a graph, starting from any node.

To learn about the faces, edges and vertices for different shapes with examples.

Breadth First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in a breadthward motion, starting from a given source vertex. It uses a queue data structure to keep track of the vertices that are yet to be explored. The algorithm works as follows:

Step 1: Begin by choosing a graph that you want to navigate.

Step 2: Select a starting vertex from which you want to traverse the graph.

Step 3: Choose two data structures to use for traversing the graph: a visited array of size equal to the number of vertices in the graph, and a queue data structure.

Step 4: Start with the chosen vertex and add it to the visited array. Enqueue all adjacent vertices of the starting vertex into the queue.

Step 5: Remove the first vertex from the queue using the FIFO (first-in-first-out) concept, add it to the visited array, and enqueue all of its unvisited adjacent vertices into the queue.

Step 6: Repeat step 5 until the queue is empty and there are no unvisited vertices left in the graph. 

Let us understand the algorithm of breadth first search with the help of an example. Consider that we will begin the traversal of the following graph from vertex 2. 

• At vertex 0, we examine all of its adjacent vertices to determine where to traverse next.
• In this case, vertex 2 is an adjacent vertex of 0.
• It is important to mark visited vertices to avoid revisiting them and getting stuck in a non-terminating process.
• Multiple BFS traversals can be performed on a graph.
• For the given graph, there are two different BFS traversals: 2,3,0,1 and 2,0,3,1.

To learn about the adjacency matrix, how to create an adjacency matrix with examples.

Breadth First Search Graph

BFS is a graph traversal algorithm that explores the graph layer by layer, starting at a given source vertex. The algorithm explores all the vertices at a particular distance from the source vertex before moving on to vertices at the next distance.

Pseudocode of implement the BFS traversal on Graph: 

Breadth_First_Search( Graph, X ) / Here, Graph is the graph that we already have and X is the source node

Let Q be the queue

Q.enqueue( X ) / Inserting source node X into the queue

Mark X node as visited.

While ( Q is not empty )

Y = Q.dequeue( ) / Removing the front node from the queue

Process all the neighbors of Y, For all the neighbors Z of Y

If Z is not visited, Q. enqueue( Z ) / Stores Z in Q

Mark Z as visited

You can implement the BFS traversal by following the method described below:

• Create a queue and add the starting vertex to it.
• Create a visited array and mark the starting vertex as visited.
• Repeat the following steps until the queue is empty:
• Remove the first vertex from the queue.
• Mark the vertex as visited.
• Add all the unvisited neighbors of the vertex to the queue.

Illustration:

Step 1: Initially the queue and visited arrays are empty.

Step 2: Push node 0 into the queue and mark it visited.

Step 3: Remove node 0 from the front of the queue and visit the unvisited neighbours and push them into the queue.

Step 4: Remove node 1 from the front of the queue and visit the unvisited neighbours and push them into the queue.

Step 5: Remove node 2 from the front of the queue and visit the unvisited neighbours and push them into the queue.

Step 6: Remove node 3 from the front of the queue and visit the unvisited neighbours and push them into the queue.

As we can see that every neighbour of node 3 is visited, so move to the next node that is in the front of the queue.

Step 7: Remove node 4 from the front of the queue and visit the unvisited neighbours and push them into the queue.

As we can see that every neighbour of node 4 is visited, so move to the next node that is in the front of the queue.

Now, the queue becomes empty, So, terminate these process of iteration.

This implementation of the BFS traversal algorithm utilizes the adjacency list representation of graphs. To store the lists of adjacent nodes and the queue of nodes required for BFS traversal, the list container of the STL (Standard Template Library) is used. 

Here is a Python implementation of the BFS (Breadth-First Search) traversal algorithm for a graph:

# Python3 Program to print BFS traversal from a given source vertex. BFS(int s) traverses 

# vertices reachable from s.

from collections import defaultdict

# This class represents a directed graph using adjacency list representation

class Graph:

# Constructor

def __init__(self):

# default dictionary to store graph

self.graph = defaultdict(list)

# function to add an edge to graph

def addEdge(self, u, v):

self.graph[u].append(v)

# Function to print a BFS of graph

def BFS(self, s):

# Mark all the vertices as not visited

visited = [False] * (max(self.graph) + 1)

# Create a queue for BFS

queue = []

# Mark the source node as

# visited and enqueue it

queue.append(s)

visited[s] = True

while queue:

# Dequeue a vertex from

# queue and print it

s = queue.pop(0)

print(s, end=" ")

# Get all adjacent vertices of the

# dequeued vertex s. If a adjacent

# has not been visited, then mark it

# visited and enqueue it

for i in self.graph[s]:

if visited[i] == False:

queue.append(i)

visited[i] = True

# Driver code

# Create a graph given in

# the above diagram

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

print(“Following is Breadth First Traversal (starting from vertex 2)”)

g.BFS(2)

Output of the program: 

Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1

To learn about the different types of graphs in graph theory, their subgraphs, properties with examples.

Explanation of the Code (Breadth-First Search - BFS)

1. Graph Representation
   The graph is shown as a dictionary where each node points to a list of its neighboring nodes. This is called an adjacency list.
2. Queue Setup
   We use a queue to keep track of which nodes to visit next. In Python, deque is used because it allows quick adding and removing of items from both ends.
3. Visited Nodes
   A set is used to keep track of the nodes we've already visited. This helps us avoid going in circles, especially if the graph has loops.
4. BFS Steps
   We take out one node at a time from the queue and look at its neighbors. If a neighbor hasn’t been visited yet, we add it to the queue and mark it as visited. This way, we go level by level from the starting point.
5. Output
   In this method, the nodes are visited in the order: A → B → C → D → E → F.

Breadth First Search for Disconnected Graph

Breadth First Search (BFS) is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the next level.

For a disconnected graph, there may be multiple connected components, i.e., subgraphs that are not connected to each other. To perform BFS on a disconnected graph, we need to apply BFS on each connected component separately.

Here's the algorithm for BFS on a disconnected graph:

• Initialise all vertices as not visited.
• For each vertex v that is not visited, apply BFS starting from v and mark all the visited vertices.
• Repeat step 2 until all vertices are visited.

To learn about connectivity in graph theory with solved problems.

To implement this algorithm, we can use a queue to store the vertices to be visited, and a boolean array to keep track of visited vertices. Here's the implementation in Python:

from collections import deque

def bfs_disconnected(graph):

n = len(graph) # number of vertices

visited = [False]*n # mark all vertices as not visited

for v in range(n):

if not visited[v]:

queue = deque([v]) # start BFS from v

visited[v] = True

while queue:

u = queue.popleft()

print(u, end=' ')

for neighbor in graph[u]:

if not visited[neighbor]:

queue.append(neighbor)

visited[neighbor] = True

print()

Breadth First Search Tree

Breadth-first search (BFS) is a popular algorithm used to traverse and search graphs and tree structures. When applied to a tree, it starts at the root node and explores all the neighboring nodes at the current level before moving on to the next level.

The BFS algorithm can be used to construct a breadth-first search tree (BFST), which is a tree that represents the order in which nodes are visited during the BFS traversal of a graph or tree.

To construct a BFS tree, we start by initializing a queue with the root node of the tree. Then, we repeatedly dequeue the front node of the queue, visit its neighbors, and add them to the queue if they have not been visited before. As we visit each node, we add it to the BFST as a child of its parent node.

The resulting tree has the same number of nodes as the original tree, but the edges are directed from parents to children, reflecting the order in which nodes are visited during the BFS traversal.

BFS trees can be useful in a variety of applications, such as network routing, shortest path algorithms, and graph visualization.

Breadth First Search Time Complexity

The time complexity of Breadth First Search (BFS) algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

In BFS, we traverse the graph level by level starting from a given source vertex. We first visit all the vertices at distance 1 from the source, then all vertices at distance 2, and so on until we have visited all vertices reachable from the source vertex.

The algorithm visits each vertex and each edge only once. Therefore, the time complexity of BFS is proportional to the sum of the number of vertices and edges in the graph, which is O(V+E).

The space complexity of BFS is O(V) because it uses an array of size V to store the BFS traversal. We also used an array of size V to keep track of visited vertices. We used a queue of size V to store the vertices.

Key Terminology in BFS

In Breadth First Search (BFS), several key terms help describe how the algorithm works. These include concepts like graphs (made of nodes and edges), queues for tracking progress, and visited sets to avoid repetition. Understanding these terms is essential to grasp how BFS explores data level by level.

Graph:
A graph is a structure made up of points (called nodes or vertices) and lines (called edges) that connect them. In BFS, this graph can go in one direction (directed) or both (undirected).

Node (Vertex):
These are the individual points in a graph. BFS starts from one node and explores other connected nodes from there.

Edge:
An edge is the line or link between two nodes. It shows which nodes are directly connected in the graph.

Queue:
This is a type of list where the first item added is the first one removed (First-In-First-Out or FIFO). BFS uses a queue to keep track of the next node to explore.

Visited Set:
To avoid checking the same node again and again, BFS keeps a list or set of nodes it has already visited.

Root or Starting Node:
This is where the BFS begins. From this node, the search spreads out to other connected nodes.

Level or Layer:
This tells how far a node is from the starting node. BFS explores all nodes one step away first, then moves to nodes two steps away, and so on.

Applications of Breadth First Search

Breadth First Search (BFS) is a powerful algorithm that can be used in various applications, some of which are:

• Breadth First Search (BFS) can find the shortest path and minimum spanning tree for unweighted graphs. In an unweighted graph, the shortest path has the least number of edges, and BFS always reaches a vertex from a source using the minimum number of edges. Any spanning tree is a minimum spanning tree in unweighted graphs, and either BFS or DFS can be used to find a spanning tree.
• BFS is used in Peer-to-Peer Networks like BitTorrent to find all neighbor nodes.
• Crawlers in Search Engines use BFS to build an index. Starting from the source page, BFS follows all links from the source and keeps doing the same. DFS can also be used, but BFS limits the depth or levels of the built tree.
• In social networking websites, BFS can find people within a given distance ‘k’ from a person by traversing ‘k’ levels.
• GPS Navigation systems use BFS to find all neighboring locations.
• Broadcasting in networks uses BFS to reach all nodes.
• In Garbage Collection, BFS is used in copying garbage collection using Cheney's algorithm because it has better locality of reference than DFS.
• BFS can be used to detect cycles in undirected graphs, and BFS can also detect cycles in directed graphs.
• In the Ford-Fulkerson algorithm, either BFS or DFS can be used to find the maximum flow, but BFS is preferred as it reduces worst-case time complexity to O(VE2).
• To test if a graph is Bipartite, BFS can be used.
• BFS can be used to find if there is a path between two vertices.
• BFS can be used to find all nodes reachable from a given node to identify all nodes within one connected component.

Comparing Breadth-First Search (BFS) with Other Algorithms

BFS vs. DFS (Depth-First Search):

• How They Work:
  BFS visits nodes one level at a time using a queue, while DFS goes deep into one branch using a stack or recursion before going back and exploring other paths.
• When to Use:
  Use BFS to find the shortest path in a graph with no weights. DFS is better for problems like solving puzzles, mazes, or ordering tasks (topological sorting).

BFS vs. Dijkstra’s Algorithm:

• Graph Type:
  BFS is suitable for graphs where all edges are the same (unweighted), while Dijkstra’s is made for graphs with different edge weights.
• When to Use:
  Use BFS for things like finding friends in a social network or checking if a graph is bipartite. Use Dijkstra’s when the path’s cost matters, like in GPS navigation or data routing in networks.

Advantages and Disadvantages of Breadth First Search

Advantages of Breadth First Search (BFS):

• BFS is guaranteed to find the shortest path between the source and any other vertex in an unweighted graph. This makes it a useful algorithm in finding the shortest distance between two points, such as in navigation or routing problems.
• BFS is a complete algorithm, which means it will always find a solution if one exists.
• BFS is used in various applications such as social network analysis, web crawling, and image processing.
• BFS can handle disconnected graphs by exploring each connected component one by one.
• BFS can be easily parallelized, which means that it can take advantage of multiple processors to speed up the search.

To learn about the distance between points, their formula and derivation with examples.

Disadvantages of Breadth First Search (BFS):

• BFS requires more memory than DFS, as it needs to store all the nodes at each level.
• Although BFS has a time complexity of O(V+E), it can be slower than DFS in practice, especially when the graph is dense.
• BFS may not be suitable for large graphs as it can become slow and memory-intensive.
• BFS may not be the best algorithm for path finding in weighted graphs, as it may not always find the shortest path.

Difference Between Breadth First Search and Depth First Search 

Breadth First Search (BFS) and Depth First Search (DFS) are two popular algorithms used for traversing or searching in a graph or tree data structure.

BFS visits all the vertices at a given level before moving to the next level, while DFS visits all the vertices along a path from the starting vertex as far as possible before backtracking. Here are some of the key differences between BFS and DFS.

In summary, BFS is a good choice when the shortest path is needed, while DFS is useful when memory usage is a concern or when finding any path between two vertices is sufficient.

Breadth First Search Solved Examples 

1.When is breadth first search optimal?

Solution:

Breadth First Search (BFS) is optimal when we want to find the shortest path between two nodes in an unweighted graph or a graph with the same weight on all edges.

BFS explores all the neighbors of a node before moving on to its neighbors' neighbors, and so on. When BFS finds the goal node, it has necessarily explored all the nodes that are at the same or shorter distance from the starting node. This guarantees that the path found by BFS is always the shortest path in terms of the number of edges between the start and goal nodes.

2. When is the breadth-first search (BFS) of a graph unique?
   Solution:
   The BFS traversal of a graph is not always unique, even if the graph is connected and undirected. This is because the order in which a node's neighbors are visited can vary, depending on how the nodes are stored and processed.

For example, if the neighbors of a node are not sorted, BFS might visit them in different orders each time, leading to different traversal outputs.

Therefore, BFS is only unique if:

• The graph is connected, and
• The adjacency list is ordered or consistently processed (e.g., sorted alphabetically or numerically).

In directed graphs, the BFS result can vary even more depending on the direction of edges and the chosen starting node.

We hope that the above article is helpful for your understanding and exam preparations. Stay tuned to the Testbook App for more updates on related topics from Mathematics, and various such subjects. Also, reach out to the test series available to examine your knowledge regarding several exams.