Here, We will discuss about Breadth First Search (BFS), their algorithms and also explain advantages, disadvantages, time complexity and their applications.

**Graph Traversals**

Graph traversal means visiting every vertex and edge exactly once in a well-defined order.

During a traversal, it is important that you track which vertices have been visited. The most common way of tracking vertices is to mark them

There are two such algorithm for traversing the graphs are:

- Breadth First Search (BFS)
- Depth First Search (DFS)

**What is Breadth First Search(BFS)?**

**Breadth First Search** **(BFS)** is a traversing algorithm for exploring a tree or graph. It works similar to* level-order traversal* of the trees. BFS works level by level.

BFS is better choice if the solution closer to the top of the tree.

This algorithm is a generalization of the *breadth-first traversal algorithm for binary trees*. It uses a queue.

** Breadth First Search(BFS) Algorithm**

BFS start traversing from a selected node(source or starting node) and traverse the graph layer-wise thus exploring the neighbour nodes (nodes which are directly connected to source node).

It continues this process until all levels of the graph are completed. *Queue* data structure is using for storing the vertices of a level.

To traverse the graph breadthwise as follow:

- First move horizontally and visit all the nodes of the current layer.
- Move to the next layer

**Advantages of Breadth First Search**

- BFS will find the
**shortest path**between the starting point and any other reachable node.

**Disadvantages of Breadth First Search**

- A BFS on a binary tree
*generally*requires more memory than a DFS.

**Time Complexity of Breadth First Search**

**Time Complexity** of Breadth First Search (BFS) is **O(V+E)** where V is the number of nodes and E is the number of edges.

If we use adjacency list for representing graphs, then Time complexity is **O(V ^{2})** for adjacency matrix representation.

**Applications of Breadth First Search(BFS) **

- Finding all connected components in a graph
- Finding all nodes within one connected component
- Find the shortest path between two nodes
- Testing a graph for bipartiteness.

### Related:

*Want to Contribute*:-

If you like “**To The Innovation**” and want to contribute, you can mail your articles to 📧 **contribute@totheinnovation.com**. See your articles on the main page and help other coders.😎