# breadth first traversals of graph

The BFS traversal of Graphs traverses the graph in levels. Breadth-first algorithm starts with the root node and then traverses all the adjacent nodes. Then, it selects the nearest node and explores all the other unvisited nodes. This process is repeated until all the nodes in the graph are explored.This technique uses the queue data structure to store the vertices or nodes and also to determine which vertex/node should be taken up next.

The BFS traversal uses an auxiliary boolean array say

The BFS traversal uses an auxiliary boolean array say

*visited[]*which keeps track of the visited vertices. That is if visited[i] = true then it means that the i-th vertex is already visited.**algorithm:**
Let S be the root/starting node of the graph.

- Step 1: Start with node S and enqueue it to the queue.
- Step 2: Repeat the following steps for all the nodes in the graph.
- Step 3: Dequeue S and process it.
- Step 4: Enqueue all the adjacent nodes of S and process them.
- [END OF LOOP]
- Step 6: EXIT

### Illustrations:

Let 0 be the starting node or source node. First, we enqueue it in the visited queue and all its adjacent nodes in the queue.

Next, we take one of the adjacent nodes to process i.e. 1. We mark it as visited by removing it from the queue and put its adjacent nodes in the queue (2 and 3 already in queue). As 0 is already visited, we ignore it.

Next, we dequeue node 2 and mark it as visited. Then, its adjacent node 4 is added to the queue.

Next, we dequeue 3 from the queue and mark it as visited. Node 3 has only one adjacent node i.e. 0 which is already visited. Hence, we ignore it.

At this stage, only node 4 is present in the queue. Its adjacent node 2 is already visited, hence we ignore it. Now we mark 4 as visited.

program: in c++:

// C++ program to implement BFS traversal // of a Graph #include <bits/stdc++.h> using namespace std; // A utility function to add an edge in an // undirected graph. void addEdge(vector<int> adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // Function to perform BFS traversal of the given Graph void BFS(vector<int> adj[], int V) { // Initialize a boolean array // to keep track of visited vertices bool visited[V + 1]; // Mark all vertices not-visited initially for (int i = 1; i <= V; i++) visited[i] = false; // Create a Queue to perform BFS queue<int> q; // Our source vertex is vertex // numbered 1 int s = 1; // Mark S visited and Push to queue visited[s] = true; q.push(s); while (!q.empty()) { // Pop element at front and print int node = q.front(); q.pop(); cout << node << " "; // Traverse the nodes adjacent to the currently // poped element and push those elements to the // queue which are not already visited for (int i = 0; i < adj[node].size(); i++) { if (visited[adj[node][i]] == false) { // Mark it visited visited[adj[node][i]] = true; // Push it to the Queue q.push(adj[node][i]); } } } } // Driver code int main() { int V = 6; vector<int> adj[V + 1]; addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 2, 4); addEdge(adj, 2, 5); addEdge(adj, 3, 5); addEdge(adj, 4, 5); addEdge(adj, 4, 6); addEdge(adj, 5, 6); BFS(adj, V); return 0; }

java:

**// Java code to illustrate BFS traversal
// in a Graph
import java.util.*;
class Graph {
// A utility function to add an edge in an
// undirected graph
static void addEdge(ArrayList<ArrayList<Integer> > adj,
int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// Function to perform BFS traversal of a Graph
static void BFS(ArrayList<ArrayList<Integer> > adj, int V)
{
// Initialize a boolean array
// to keep track of visited vertices
boolean visited[] = new boolean[V+1];
// Mark all vertices not-visited initially
for (int i = 1; i <= V; i++)
visited[i] = false;
// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();
// The start vertex or source vertex is 1
int s = 1;
// Mark the current node as
// visited and enqueue it
visited[s]=true;
queue.add(s);
while (queue.size() != 0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();
System.out.print(s+" ");
// Traverse the nodes adjacent to the currently
// poped element and push those elements to the
// queue which are not already visited
for (int i = 0; i < adj.get(s).size(); i++) {
// Fetch adjacent node
int newNode = adj.get(s).get(i);
// Check if it is not visited
if(visited[newNode] == false)
{
// Mark it visited
visited[newNode] = true;
// Add it to queue
queue.add(newNode);
}
}
}
}
// Driver Code
public static void main(String[] args)
{
// Creating a graph with 6 vertices
int V = 6;
ArrayList<ArrayList<Integer> > adj
= new ArrayList<ArrayList<Integer> >(V+1);
for (int i = 0; i < V+1; i++)
adj.add(new ArrayList<Integer>());
// Adding edges one by one
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 2, 4);
addEdge(adj, 2, 5);
addEdge(adj, 3, 5);
addEdge(adj, 4, 5);
addEdge(adj, 4, 6);
addEdge(adj, 5, 6);
BFS(adj, V);
}
}
**