Skip to main content

Breadth First Search (BFS)

 

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.

BFS uses a queue data structure to hold the next nodes to visit. The first node visited is the root node, and then it visits all the neighbor nodes at the present depth level from left to right, and adds them to the queue. Then it visits the next level nodes and continues the same process until it reaches the end of the tree or graph.


BFS can be used to solve many problems in graph theory, for example:

  • Finding the shortest path between two nodes u and v, with the condition that the path is the shortest among all possible paths. This can be done using a predecessor subgraph.
  • Testing a graph for bipartiteness.
  • Finding all connected components in an undirected graph.
  • Finding the level of each node in a tree.
  • Finding the shortest path from a node to all other nodes.


BFS can also be used to solve problems in artificial intelligence, such as:

  • Finding the shortest path to a target location in a game.
  • Generating a maze.
  • Solving a Rubik's Cube using the "layer by layer" method.


However, the main drawback of the BFS algorithm is its space complexity, as it needs to store all the generated nodes in the memory, which can be very large for big graphs. To overcome this problem, one can use an iterative version of the BFS, called iterative deepening depth-first search (IDDFS), which applies a depth-first search with increasing depth limits.

In summary, Breadth-first search is a simple and easy to understand algorithm that can be used to solve many problems in graph theory, artificial intelligence, and other fields. It has a time complexity of O(V+E) and space complexity of O(V) where V is the number of vertices and E is the number of edges.


ALGORITHM:

Breadth-first search (BFS) is a traversal algorithm used to explore all the vertices of a graph or a tree in breadth-first order. It starts at a given source vertex and explores all the vertices at the same level as the source vertex before moving on to the vertices at the next level.


Here is the general algorithm for BFS:

  1. Create a queue and enqueue the source vertex.
  2. Mark the source vertex as visited.
  3. While the queue is not empty:

  • Dequeue a vertex from the queue.
  • For each unvisited neighbor of the dequeued vertex, mark it as visited and enqueue it.

Repeat steps 3a and 3b until all the vertices have been visited.

BFS can be implemented using an adjacency list or an adjacency matrix to represent the graph.


PSEUDO CODE:

Here is a pseudocode for the Breadth-first search (BFS) algorithm for traversing a graph:


The input to the algorithm is the graph G represented using an adjacency list or an adjacency matrix, and the starting vertex 'start_vertex'.
The output is a set of visited vertices 'V' in breadth-first order.

This algorithm uses a queue to keep track of vertices to visit next, and a set to keep track of visited vertices. The algorithm starts by adding the starting vertex to the queue and the set of visited vertices. Then, it enters a loop that continues until the queue is empty. In each iteration of the loop, a vertex is dequeued from the queue, and all of its unvisited neighbors are added to the queue and the set of visited vertices. This way, the algorithm visits all the vertices of the graph in breadth-first order.

In this way, BFS explores all the neighbor vertex of the current vertex before it goes deeper in the graph.

Please note that this pseudocode can be customized and optimized depending on the problem that you want to solve.


PYTHON CODE:

Here is an example of the Breadth-first search (BFS) algorithm implemented in Python using an adjacency list to represent the graph:



In this example, the input to the BFS function is a graph represented using an adjacency list and a starting vertex. The function initializes an empty set to keep track of visited vertices, and a queue to keep track of vertices to visit next. It starts by adding the starting vertex to the set of visited vertices and the queue. Then, it enters a loop that continues until the queue is empty. In each iteration of the loop, a vertex is dequeued from the queue, and all of its unvisited neighbors are added to the queue and the set of visited vertices. This way, the algorithm visits all the vertices of the graph in breadth-first order.

Please note that this is a basic example and it can be customized and optimized depending on the problem that you want to solve.

Also note that, Python's built-in deque class is used to implement the queue, it provides an efficient way to add and remove elements from both ends of the queue.

JAVA CODE:

Here is an example of the Breadth-first search (BFS) algorithm implemented in Java using an adjacency list to represent the graph:


In this example, the input to the bfs function is a graph represented using an adjacency list and a starting vertex. The function initializes an empty set to keep track of visited vertices, and a queue to keep track of vertices to visit next. It starts by adding the starting vertex to the set of visited vertices and the queue. Then, it enters a loop that continues until the queue is empty. In each iteration of the loop, a vertex is dequeued from the queue, and all of its unvisited neighbors are added to the queue and the set of visited vertices. This way, the algorithm visits all the vertices of the graph in breadth-first order.

Please note that this is a basic example and it can be customized and optimized depending on the problem that you want to solve.

Also, java provides two built-in classes that can be used to implement a queue, LinkedList and PriorityQueue, where LinkedList is used in this example.

C CODE:

Here is an example of the Breadth-first search (BFS) algorithm implemented in C using an adjacency list to represent the graph:


In this example, the input to the BFS function is a graph represented using an adjacency matrix and a starting vertex, and the number of vertices. The function initializes an array to keep track of visited vertices, and a queue to keep track of vertices to visit next. It starts by adding the starting vertex to the queue and marking it as visited. Then, it enters a loop that continues until the queue is empty. In each iteration of the loop, a vertex is dequeued from the queue, and all of its unvisited neighbors are added to the queue and marked as visited. This way, the algorithm visits all the vertices of the graph in breadth-first order.

Please note that this is a basic example and it can be customized and optimized depending on the problem that you want to solve.

Also, in this example, the queue is implemented using an array, with three variables front, rear, and data. front and rear are used to keep track of the head and tail of the queue, and data is used to store the elements in the queue.

C++ CODE:

Here is an example of the Breadth-first search (BFS) algorithm implemented in C++ using an adjacency list to represent the graph:


In this example, the input to the BFS function is a graph represented using an adjacency list and a starting vertex. The function initializes an vector to keep track of visited vertices, and a queue to keep track of vertices to visit next. It starts by adding the starting vertex to the queue and marking it as visited. Then, it enters a loop that continues until the queue is empty. In each iteration of the loop, a vertex is dequeued from the queue, and all of its unvisited neighbors are added to the queue and marked as visited. This way, the algorithm visits all the vertices of the graph in breadth-first order.

Please note that this is a basic example and it can be customized and optimized depending on the problem that you want to solve.

Also, in this example, queue is implemented using C++ STL's queue.

JAVASCRIPT CODE:

Here is an example of the Breadth-first search (BFS) algorithm implemented in JavaScript using an adjacency list to represent the graph:



In this example, the input to the BFS function is a graph represented using an adjacency list and a starting vertex. The function initializes an empty set to keep track of visited vertices, and a queue to keep track of vertices to visit next. It starts by adding the starting vertex to the set of visited vertices and the queue. Then, it enters a loop that continues until the queue is empty. In each iteration of the loop, a vertex is dequeued from the queue, and all of its unvisited neighbors are added to the queue and the set of visited vertices. This way, the algorithm visits all the vertices of the graph in breadth-first order.

Please note that this is a basic example and it can be customized and optimized depending on the problem that you want to solve.

Also, in this example, JavaScript's built-in Set class and Array is used to implement the set and queue.

Comments

Post a Comment

Popular posts from this blog

Selection Sort

Selection sort is a simple sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. It is called selection sort because it repeatedly selects the smallest element of the unsorted portion of the array and moves it to its correct position in the sorted portion of the array. The time complexity of selection sort is O(n^2), where n is the number of elements in the array. This makes it inefficient for large arrays and it is not a good choice for sorting large datasets. However, selection sort is easy to understand and implement, and it is useful for educational purposes and for small arrays. One of the advantages of selection sort is that it makes fewer swaps than other sorting algorithms such as bubble sort. This makes it more efficient in terms of memory writes, which can be important in some situations. Another advantage of selection sort is that it is a stable so
2 comments
Read more

Counting Sort

Counting sort is a sorting algorithm that operates by counting the frequency of each element in the input array, and then using these frequencies to compute the final sorted output. The algorithm works by first creating an array of counters, with each counter corresponding to a distinct element in the input array. The counters are initialized to zero, and then the input array is scanned once to count the number of occurrences of each element. This count information is stored in the corresponding counter in the counter array. Once the count information is obtained, the algorithm uses it to determine the final position of each element in the sorted output array. This is done by iterating over the counter array, and for each counter value, writing the corresponding element to the sorted output array the appropriate number of times. The time complexity of counting sort is O(n+k), where n is the length of the input array and k is the range of the elements. The space complexity is also O(n+k
2 comments
Read more

Pigeonhole Sort

Pigeonhole sort is a sorting algorithm that works by distributing elements of an input sequence into a set of pigeonholes or buckets. It is an efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Pigeonhole sort is an example of a bucket sort algorithm. The pigeonhole sort algorithm works by first determining the range of values in the input sequence. This range is used to create a set of pigeonholes or buckets, each of which can hold one or more elements from the input sequence. Each element in the input sequence is then placed into its corresponding pigeonhole based on its value. If two or more elements have the same value, they can be placed in the same pigeonhole. Once all the elements have been placed into their corresponding pigeonholes, the elements are sorted within each pigeonhole. Finally, the sorted elements are combined into a single output sequence. Pigeonhole sort has a time complexity
Post a Comment
Read more