BFS यानि Breadth First Search

BFS एक तालाब में फैलती ripples जैसा है: यह पहले आपके सबसे करीबी friends visit करता है, फिर friends के friends, level by level बाहर जाते हुए।

In this page:

What is BFS
Queue in BFS
Visited Array
BFS Uses
Complexity

Syntax

markup

from collections import deque
visited = {start}
queue = deque([start])
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

What is BFS

Breadth-first search (BFS) किसी graph को level by level explore करता है, किसी vertex के सभी direct neighbors visit करने के बाद उनके neighbors की ओर move करते हुए — यह level-by-level order वह है जो edges की संख्या के लिहाज़ से shortest path ढूंढने की गारंटी देता है।

उदाहरण: What is BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
	vector<vector<int>> adj = {{1,2},{0,3},{0,3},{1,2}};
	queue<int> q; vector<bool> visited(4,false);
	q.push(0); visited[0]=true;
	cout << "Level order from 0: ";
	while (!q.empty()) {
		int u = q.front(); q.pop(); cout << u << " ";
		for (int v : adj[u]) if (!visited[v]) { visited[v]=true; q.push(v); }
	}
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		List<List<Integer>> adj = Arrays.asList(Arrays.asList(1,2), Arrays.asList(0,3), Arrays.asList(0,3), Arrays.asList(1,2));
		Queue<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[4];
		q.add(0); visited[0] = true;
		System.out.print("Level order from 0: ");
		while (!q.isEmpty()) {
			int u = q.poll(); System.out.print(u + " ");
			for (int v : adj.get(u)) if (!visited[v]) { visited[v] = true; q.add(v); }
		}
	}
}

from collections import deque
adj = [[1,2],[0,3],[0,3],[1,2]]
visited = [False]*4
q = deque([0]); visited[0] = True
print("Level order from 0:", end=" ")
while q:
    u = q.popleft()
    print(u, end=" ")
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            q.append(v)

#include <stdio.h>
int main() {
	int adj[4][2] = {{1,2},{0,3},{0,3},{1,2}};
	int queue[4], front=0, back=0, visited[4]={0};
	queue[back++]=0; visited[0]=1;
	printf("Level order from 0: ");
	while (front < back) {
		int u = queue[front++];
		printf("%d ", u);
		for (int i = 0; i < 2; i++) {
			int v = adj[u][i];
			if (!visited[v]) { visited[v]=1; queue[back++]=v; }
		}
	}
	return 0;
}

Queue in BFS

एक queue traversal drive करता है: source vertex को enqueue करके शुरू करें, फिर बार-बार एक vertex dequeue करें, इसे process करें, और इसके किसी भी unvisited neighbors को enqueue करें — चूंकि queue first-in-first-out है, vertices naturally source से distance के order में process होते हैं।

उदाहरण: Queue in BFS

#include <iostream>
#include <queue>
using namespace std;
int main() {
	queue<int> q;
	q.push(5); q.push(3); q.push(8);
	cout << "First out (FIFO): " << q.front();
	q.pop();
	cout << ", next: " << q.front();
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Queue<Integer> q = new LinkedList<>();
		q.add(5); q.add(3); q.add(8);
		System.out.print("First out (FIFO): " + q.poll());
		System.out.println(", next: " + q.peek());
	}
}

from collections import deque
q = deque([5, 3, 8])
first = q.popleft()
print(f"First out (FIFO): {first}, next: {q[0]}")

#include <stdio.h>
int main() {
	int queue[3] = {5, 3, 8}, front = 0;
	int firstOut = queue[front++];
	printf("First out (FIFO): %d, next: %d", firstOut, queue[front]);
	return 0;
}

Visited Array

एक visited array (या set) हर vertex को उसके enqueue होते ही मार्क करता है, इसे एक अलग path से बाद में फिर queue में जुड़ने से रोकते हुए — इसके बिना, BFS एक cycle वाले graph पर उसी vertex को बार-बार process कर सकता है और कभी terminate नहीं हो सकता।

उदाहरण: Visited Array

#include <iostream>
using namespace std;
int main() {
	bool visited[5] = {false};
	int vertex = 2;
	if (!visited[vertex]) { visited[vertex] = true; cout << vertex << " marked visited, enqueued once"; }
	if (visited[vertex]) cout << " -- re-enqueue attempt skipped";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		boolean[] visited = new boolean[5];
		int vertex = 2;
		if (!visited[vertex]) { visited[vertex] = true; System.out.print(vertex + " marked visited, enqueued once"); }
		if (visited[vertex]) System.out.print(" -- re-enqueue attempt skipped");
	}
}

visited = [False] * 5
vertex = 2
if not visited[vertex]:
    visited[vertex] = True
    print(f"{vertex} marked visited, enqueued once", end="")
if visited[vertex]:
    print(" -- re-enqueue attempt skipped")

#include <stdio.h>
int main() {
	int visited[5] = {0};
	int vertex = 2;
	if (!visited[vertex]) { visited[vertex] = 1; printf("%d marked visited, enqueued once", vertex); }
	if (visited[vertex]) printf(" -- re-enqueue attempt skipped");
	return 0;
}

BFS Uses

चूंकि BFS source से बढ़ती distance के सख्त order में explore करता है, यह unweighted graphs में shortest paths ढूंढने के लिए standard tool है — किसी vertex तक पहली बार पहुंचना guaranteed है कि यह एक shortest possible path से है।

उदाहरण: BFS Uses

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
	vector<vector<int>> adj = {{1,2},{0,3},{0,3},{1,2}};
	vector<int> dist(4, -1);
	queue<int> q; q.push(0); dist[0] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u]+1; q.push(v); }
	}
	cout << "Shortest hops from 0 to 3: " << dist[3];
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		List<List<Integer>> adj = Arrays.asList(Arrays.asList(1,2), Arrays.asList(0,3), Arrays.asList(0,3), Arrays.asList(1,2));
		int[] dist = {0,-1,-1,-1};
		Queue<Integer> q = new LinkedList<>(); q.add(0);
		while (!q.isEmpty()) {
			int u = q.poll();
			for (int v : adj.get(u)) if (dist[v] == -1) { dist[v] = dist[u]+1; q.add(v); }
		}
		System.out.println("Shortest hops from 0 to 3: " + dist[3]);
	}
}

from collections import deque
adj = [[1,2],[0,3],[0,3],[1,2]]
dist = [-1]*4
dist[0] = 0
q = deque([0])
while q:
    u = q.popleft()
    for v in adj[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)
print("Shortest hops from 0 to 3:", dist[3])

#include <stdio.h>
int main() {
	int adj[4][2] = {{1,2},{0,3},{0,3},{1,2}};
	int dist[4] = {0,-1,-1,-1}, queue[4], front=0, back=0;
	queue[back++] = 0;
	while (front < back) {
		int u = queue[front++];
		for (int i = 0; i < 2; i++) {
			int v = adj[u][i];
			if (dist[v] == -1) { dist[v] = dist[u]+1; queue[back++] = v; }
		}
	}
	printf("Shortest hops from 0 to 3: %d", dist[3]);
	return 0;
}

Complexity

एक adjacency list के साथ, BFS O(V + E) time में चलता है, क्योंकि पूरी traversal में हर vertex एक बार enqueued होता है और हर edge एक बार examine होता है — यह linear-in-graph-size behavior है जो BFS को काफी बड़े graphs पर भी practical बनाता है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "BFS with adjacency list: O(V + E) time, each vertex enqueued once, each edge examined once";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("BFS with adjacency list: O(V + E) time, each vertex enqueued once, each edge examined once");
	}
}

print("BFS with adjacency list: O(V + E) time, each vertex enqueued once, each edge examined once")

#include <stdio.h>
int main() {
	printf("BFS with adjacency list: O(V + E) time, each vertex enqueued once, each edge examined once");
	return 0;
}

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Graph Representation Next Lesson → DFS Depth First Search