Understand Breadth First Search Problem

Problem Name: Breadth First Search

Problem Description:

Breadth-First Search (BFS) Explained

Breadth-First Search (BFS) is a fundamental graph traversal algorithm. It explores the graph level by level, starting from a given source node and expanding outwards to all its neighbours before moving on to the next level.

Example:

INPUT : [ [0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 1], [0, 0, 0, 1] ] , 2 graph

OUTPUT: 2 -> 0 -> 1 -> 3

Key Concepts

Graph Structure:
BFS works on graphs (both directed and undirected) as well as trees.
Level-Order Traversal:
Nodes are visited in order of their distance from the starting node (i.e., by increasing number of edges).
Queue Data Structure:
BFS uses a FIFO (first-in, first-out) queue to keep track of nodes to visit next.

How BFS Works

Initialization:
- Mark the starting node as visited.
- Enqueue the starting node.
Iteration:
- Dequeue a node from the front of the queue.
- Process the current node (e.g., record its value).
- For each unvisited neighbour of the current node:
  - Mark the neighbour as visited.
  - Enqueue the neighbour.
Termination:
- Repeat the iteration until the queue is empty. At this point, all reachable nodes from the starting node have been visited.

Time and Space Complexity

Time Complexity: O(V + E)

V = number of vertices
E = number of edges
Every vertex and edge is processed once.

Space Complexity: O(V)

In the worst case, the queue holds all vertices in the graph.

Applications of BFS

Shortest Path:
BFS is ideal for finding the shortest path in unweighted graphs.
Level Order Traversal:
In trees, BFS performs a level order traversal.
Connected Components:
BFS can help determine the connected components in a graph.
Web Crawlers:
Used to explore the web layer by layer starting from a seed URL.

Category:
Graphs
Searching

Programming Language:
Java

Reference Link:

https://drawtocode.vercel.app/problems/breadth-first-search

Online IDE

Scroll down for output

Java

Output:

Loading component...

Tracking code (View only. In case you want to track the code, click this button):

Main Function:

INPUT: [ 0 ->[ 1, 2 ] , 1 -> [2] , 2 -> [ 0 , 3], 3 -> [3] ] , 2 , 4

OUTPUT: 2,0,1,3

public static void main(String[] args) {

int numVertices = 6;

List<Integer>[] graph = new ArrayList[numVertices];

for (int i = 0; i < numVertices; i++) {

graph[i] = new ArrayList<>();

}//Loop End

graph[0].add(1);

graph[0].add(2);

graph[1].add(0);

graph[1].add(3);

graph[1].add(4);

graph[2].add(0);

graph[2].add(5);

graph[3].add(1);

graph[4].add(1);

graph[4].add(5);

graph[5].add(2);

graph[5].add(4);

System.out.println("BFS starting from node 0:");

bfs(graph, 0, numVertices);

} //Function End

Helper Function:

public static void bfs(List<Integer>[] graph, int start, int numVertices) {

boolean[] visited = new boolean[numVertices];

Queue<Integer> queue = new LinkedList<>();

visited[start] = true;

queue.add(start);

while (!queue.isEmpty()) {

int current = queue.poll();

System.out.print(current + " ");

for (int neighbor : graph[current]) {

if (!visited[neighbor]) {

visited[neighbor] = true;

queue.add(neighbor);

}//If End