# What Is BFS Algorithm in Data Structure?

//

Angela Bailey

What Is BFS Algorithm in Data Structure?

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the current level before moving to the next level. It is commonly used to find the shortest path between two nodes or to traverse a tree or graph in a systematic way.

## How Does BFS Algorithm Work?

The BFS algorithm starts by selecting an arbitrary vertex as the starting point and adds it to a queue. Then, it explores all the neighboring vertices of the current vertex before moving on to the next level. The algorithm continues this process until all vertices have been visited.

BFS uses a queue data structure to keep track of which vertices to visit next. It follows these steps:

• Step 1: Start by selecting a starting vertex and mark it as visited.
• Step 2: Enqueue the starting vertex into a queue.
• Step 3: Repeat steps 4-7 until the queue becomes empty.
• Step 4: Dequeue a vertex from the front of the queue.
• Step 5: Explore all its neighboring vertices that have not been visited yet.
• Step 6: Mark each neighboring vertex as visited and enqueue it into the queue.
• Step 7: Repeat steps 4-6 until there are no more neighbors to explore.

## The Benefits of BFS Algorithm

The BFS algorithm has several advantages:

• Shortest Path: BFS guarantees that it will find the shortest path between two nodes in an unweighted graph.
• Completeness: If there is a path between two nodes, BFS will always find it.
• Tree and Graph Traversal: BFS can be used to traverse not only trees but also graphs (both directed and undirected).

## Implementation of BFS Algorithm

Here is a simple implementation of the BFS algorithm in Python:

def bfs(graph, start):
visited = set()
queue = []

queue.append(start)

while queue:
vertex = queue.pop(0)
print(vertex, end=" ")

for neighbor in graph[vertex]:
if neighbor not in visited: