WikiGalaxy
Graph Traversal: Breadth-First Search (BFS)
Introduction to BFS
Breadth-First Search (BFS) is a fundamental algorithm for traversing or searching tree or graph data structures. It starts at the root node and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
Key Concepts of BFS
BFS uses a queue data structure to keep track of nodes to be explored. It is particularly useful for finding the shortest path in an unweighted graph.
import java.util.*;
class Graph {
private int V;
private LinkedList adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void BFS(int s) {
boolean visited[] = new boolean[V];
LinkedList queue = new LinkedList();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll();
System.out.print(s + " ");
Iterator i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
}
public class Example {
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Following is Breadth First Traversal " +
"(starting from vertex 2)");
g.BFS(2);
}
}
Example Explanation
In this example, we have a graph with 4 vertices. The BFS traversal starting from vertex 2 visits nodes in the order: 2, 0, 3, 1. This demonstrates how BFS explores all neighbor nodes at the present depth before moving on to the next level.
Console Output:
Following is Breadth First Traversal (starting from vertex 2): 2 0 3 1
BFS for Shortest Path in Unweighted Graph
Shortest Path with BFS
BFS is ideal for finding the shortest path in an unweighted graph because it explores all nodes at the present depth level before moving on to the next level, ensuring the shortest path is found.
import java.util.*;
class ShortestPathGraph {
private int V;
private LinkedList adj[];
ShortestPathGraph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
int[] bfsShortestPath(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
LinkedList queue = new LinkedList<>();
dist[src] = 0;
queue.add(src);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj[node]) {
if (dist[neighbor] == Integer.MAX_VALUE) {
dist[neighbor] = dist[node] + 1;
queue.add(neighbor);
}
}
}
return dist;
}
}
public class Example {
public static void main(String args[]) {
ShortestPathGraph g = new ShortestPathGraph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(3, 4);
int[] distances = g.bfsShortestPath(0);
System.out.println("Shortest distances from node 0:");
for (int i = 0; i < distances.length; i++) {
System.out.println("To node " + i + " is " + distances[i]);
}
}
}
Example Explanation
This example calculates the shortest path from node 0 to all other nodes in an unweighted graph. The BFS ensures that the shortest path is found by exploring nodes level by level.
Console Output:
Shortest distances from node 0: To node 0 is 0 To node 1 is 1 To node 2 is 1 To node 3 is 2 To node 4 is 3
BFS for Level Order Traversal in Trees
Level Order Traversal
BFS can be used to perform a level order traversal on a tree, visiting nodes level by level from left to right.
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
left = right = null;
}
}
class Tree {
TreeNode root;
void levelOrderTraversal() {
if (root == null) return;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
}
public class Example {
public static void main(String args[]) {
Tree tree = new Tree();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
System.out.println("Level order traversal of binary tree is:");
tree.levelOrderTraversal();
}
}
Example Explanation
In this example, BFS is used to perform a level order traversal of a binary tree. The nodes are visited level by level, which is a common use case for BFS in tree structures.
Console Output:
Level order traversal of binary tree is: 1 2 3 4 5
Detecting Cycles in Undirected Graph using BFS
Cycle Detection with BFS
BFS can be utilized to detect cycles in an undirected graph by checking if a visited node is reached again through a different path.
import java.util.*;
class CycleGraph {
private int V;
private LinkedList adj[];
CycleGraph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
boolean isCyclic() {
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (isCyclicUtil(i, visited, -1))
return true;
}
}
return false;
}
boolean isCyclicUtil(int v, boolean visited[], int parent) {
visited[v] = true;
Integer i;
Iterator it = adj[v].iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i]) {
if (isCyclicUtil(i, visited, v))
return true;
} else if (i != parent)
return true;
}
return false;
}
}
public class Example {
public static void main(String args[]) {
CycleGraph g = new CycleGraph(5);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 1);
if (g.isCyclic())
System.out.println("Graph contains cycle");
else
System.out.println("Graph doesn't contain cycle");
}
}
Example Explanation
This example demonstrates how BFS can be used to detect cycles in an undirected graph. By keeping track of visited nodes and their parents, the algorithm identifies if a node is revisited through a different path, indicating a cycle.
Console Output:
Graph contains cycle
BFS for Bipartite Graph Checking
Bipartite Graph Check
A graph is bipartite if its vertices can be divided into two disjoint sets such that no two graph vertices within the same set are adjacent. BFS can be used to check this property.
import java.util.*;
class BipartiteGraph {
private int V;
private LinkedList adj[];
BipartiteGraph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
boolean isBipartite(int src) {
int[] colors = new int[V];
Arrays.fill(colors, -1);
colors[src] = 1;
LinkedList queue = new LinkedList<>();
queue.add(src);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj[u]) {
if (colors[v] == -1) {
colors[v] = 1 - colors[u];
queue.add(v);
} else if (colors[v] == colors[u])
return false;
}
}
return true;
}
}
public class Example {
public static void main(String args[]) {
BipartiteGraph g = new BipartiteGraph(4);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 0);
if (g.isBipartite(0))
System.out.println("Graph is Bipartite");
else
System.out.println("Graph is not Bipartite");
}
}
Example Explanation
This example checks if a graph is bipartite using BFS. The algorithm assigns colors to nodes and checks adjacent nodes for color conflicts. If a conflict is found, the graph is not bipartite.
Console Output:
Graph is Bipartite
