In this article, you will learn to implement a Breadth-First Search (BFS) algorithm on a graph by using Java with iterative approaches

Breadth-First Search (BFS) is an algorithm for traversing and searching for a graph/tree layer-wise. It starts at an arbitrary node and explores all of the neighbor nodes before moving to the next depth level

Let's get started!

### Problem

• Give an undirected/directed graph G(V, E)

• Write a Breadth-First search algorithm to print out each vertex value exactly once

### Example

For the above graph with 0 as the starting vertex, assuming that the left edges are chosen before the right edges, the BFS traversal order will be 0 -> 1 -> 2 -> 3 -> 4

### Approach 1: Iterative

• Use an array to track visited nodes to avoid processing a node more than once

• Use a queue to track which nodes to visit next

``````
``````

`GraphUndirectedByAdjacencyList` is defined in Graph Data Structure

• Output
``````0 1 2 3 4
``````
• Time complexity: O(V+E)

• Space complexity: O(V)

### Approach 2: Iterative with Color

• Use a color array to track vertex states. Each vertex can have 3 states marked by color

• White represents unvisited

• Gray represents a visit in progress

• Black represents visited

• Use a queue to track which nodes to visit next

``````
``````

`GraphUndirectedByAdjacencyList` is defined in Graph Data Structure

• Output
``````0 1 2 3 4
``````
• Time complexity: O(V+E)

• Space complexity: O(V)

### Applications

• Find shortest paths between vertices

The shortest path is a path between two vertices in a graph such that the total sum of the weights of the constituent edges is minimum

You can implement an algorithm to find the shortest path by using Breadth-First Search (BFS), Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms