Graph Algorithms: Breadth-First Search (BFS) in Java
Implementation and applications of Breadth-First Search (BFS) algorithm in Java for graph traversal and solving problems like shortest path in unweighted graphs.
BFS Time and Space Complexity in Competitive Programming
Breadth-First Search (BFS) is a fundamental graph traversal algorithm used to systematically explore the nodes of a graph layer by layer. It's particularly useful for finding the shortest path in an unweighted graph. Understanding its time and space complexity is crucial for efficient problem-solving in competitive programming.
Time Complexity of BFS
The time complexity of BFS is typically expressed as O(V + E), where:
- V represents the number of vertices (nodes) in the graph.
- E represents the number of edges in the graph.
Explanation:
- Each vertex is visited and enqueued at most once. This accounts for the
O(V)part. - For each visited vertex, we iterate through its adjacency list to explore its neighbors. In total, across all vertices, we consider each edge at most twice (once for each endpoint). This contributes to the
O(E)part.
In the worst-case scenario, where the graph is dense (i.e., has many edges), E can be close to V2, making the time complexity O(V + V2) = O(V2).
Space Complexity of BFS
The space complexity of BFS is primarily determined by the size of the queue used to store the vertices to be visited. In the worst-case scenario, the queue might contain all the vertices in the graph. Therefore, the space complexity is O(V).
Explanation:
- The queue holds the vertices that are waiting to be processed.
- In the worst case (e.g., a complete graph), all vertices might be added to the queue simultaneously before any are dequeued.
- Additionally, we may use a visited array (or similar data structure) to track visited nodes, which also takes O(V) space.
Analyzing the Impact on Performance
Understanding the time and space complexity helps us predict how BFS will perform with different input sizes. Here's how to analyze its impact:
- Large Graphs: For very large graphs (e.g., graphs with millions of vertices and edges), the
O(V + E)time complexity can become a bottleneck. If the graph is dense, theO(V2)complexity might be prohibitive. - Memory Usage: The
O(V)space complexity means that BFS might consume a significant amount of memory, especially for graphs with a large number of vertices. Consider memory constraints in competitive programming problems. - Optimization Techniques: In some cases, you can optimize BFS by using techniques such as:
- Bidirectional BFS: Performing BFS from both the start and end nodes simultaneously can significantly reduce the search space, especially in certain types of graphs.
- Adjacency List vs. Adjacency Matrix: Choosing the right data structure to represent the graph can impact performance. Adjacency lists are often preferred for sparse graphs, while adjacency matrices might be more suitable for dense graphs when fast existence checking is needed.
BFS Implementation in Java with Examples
Example 1: Simple BFS on a Graph
This example demonstrates a basic BFS implementation on a graph represented using an adjacency list.
import java.util.*;
class Graph {
private int V; // Number of vertices
private LinkedList<Integer> adj[]; // Adjacency Lists
// Constructor
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w);
}
// Prints BFS traversal from a given source s
void BFS(int s) {
// Mark all the vertices as not visited(By default
// set as false)
boolean visited[] = new boolean[V];
// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();
// 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 + " ");
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
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);
}
} Explanation: The code defines a `Graph` class that represents a graph using an adjacency list. The `BFS` method performs the breadth-first search starting from a given source node. It uses a queue to keep track of the nodes to be visited and a `visited` array to avoid revisiting nodes.
Example 2: Finding the Shortest Path in an Unweighted Graph
This example demonstrates how to use BFS to find the shortest path from a source node to all other nodes in an unweighted graph.
import java.util.*;
class ShortestPath {
private int V; // Number of vertices
private LinkedList<Integer> adj[]; // Adjacency Lists
// Constructor
ShortestPath(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w);
}
// Function to find shortest paths from source to all other vertices
int[] shortestPath(int s) {
int[] dist = new int[V];
Arrays.fill(dist, -1); // Initialize distances to -1 (unreachable)
Queue<Integer> queue = new LinkedList<>();
dist[s] = 0; // Distance from source to itself is 0
queue.add(s);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj[u]) {
if (dist[v] == -1) { // If v is not visited
dist[v] = dist[u] + 1; // Update distance
queue.add(v);
}
}
}
return dist;
}
public static void main(String args[]) {
ShortestPath g = new ShortestPath(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
int source = 0;
int[] distances = g.shortestPath(source);
System.out.println("Shortest paths from vertex " + source + ":");
for (int i = 0; i < distances.length; i++) {
System.out.println("Vertex " + i + ": " + distances[i]);
}
}
} Explanation: The `shortestPath` method calculates the shortest distance from the source node `s` to all other nodes in the graph. It uses a `dist` array to store the distances, initialized to -1 for unreachable nodes. The algorithm then performs BFS, updating the `dist` array as it explores the graph. The distance to a neighbor node `v` is updated as `dist[v] = dist[u] + 1`, where `u` is the current node being visited.
Example 3: Competitive Programming scenario: Flood Fill
This example uses BFS to solve the flood fill problem which is useful for counting connected components or finding areas in a grid.
import java.util.*;
class FloodFill {
public static int floodFill(char[][] grid, int row, int col) {
int rows = grid.length;
int cols = grid[0].length;
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] != '1') {
return 0; // Base case: out of bounds or not part of the island
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{row, col});
grid[row][col] = '0'; // Mark as visited
int area = 0;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0];
int c = cell[1];
area++;
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Right, Left, Down, Up
for (int[] dir : directions) {
int newRow = r + dir[0];
int newCol = c + dir[1];
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1') {
queue.offer(new int[]{newRow, newCol});
grid[newRow][newCol] = '0'; // Mark as visited
}
}
}
return area;
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
int islandRow = 0; // Starting row for the island
int islandCol = 0; // Starting column for the island
int islandArea = floodFill(grid, islandRow, islandCol);
System.out.println("Area of the island: " + islandArea);
//This will modify the grid. If you need to preserve the grid you will need to create a copy.
char[][] grid2 = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
int numberOfIslands = countIslands(grid2);
System.out.println("Number of islands: " + numberOfIslands);
}
public static int countIslands(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int islandCount = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
floodFill(grid, i, j); // Explore the island starting from this cell
islandCount++;
}
}
}
return islandCount;
}
} Explanation: The `floodFill` function uses BFS to find the connected components in the grid. If the grid location contains a '1' and it has not been visited yet, it will mark the current cell as visited. The program then uses the grid location and the `floodFill` function to count the total number of islands.
Conclusion
Understanding the time and space complexity of BFS is essential for writing efficient and performant code, especially in competitive programming. By considering the size of the input graph and potential optimizations, you can choose the right approach to solve graph-related problems effectively.