BFS Traversal
Breadth-First Search (BFS) explores a graph level by level, like spreading ripples in water. It uses a queue and is used for finding shortest paths in unweighted graphs.
Algorithm:
1. Start from source node, mark visited, enqueue it.
2. While queue not empty:
- Dequeue node u.
- For each neighbor v of u, if not visited, mark visited, enqueue v.
Java implementation for adjacency list:
public void bfs(int start) {
boolean[] visited = new boolean[V];
Queue queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int u = queue.poll();
System.out.print(u + " ");
for (int v : adjList[u]) {
if (!visited[v]) {
visited[v] = true;
queue.offer(v);
}
}
}
}
Time complexity: O(V+E) for adjacency list.
Two Minute Drill
- BFS explores nodes level by level using a queue.
- Finds shortest path in unweighted graphs.
- Visited array prevents cycles.
- Time O(V+E), space O(V).
Need more clarification?
Drop us an email at career@quipoinfotech.com