BFS

Complete

Summary

Breadth first search(BFS)

iterative, queue

Time complexity

using an adjacency list
same as DFS
average case: - every time a vertex is dequeued, check all neighbours

Concept

Algorithm

enqueue every neighbour into a queue
while the queue is not empty, dequeue the first vertex and enqueue its neighbours

java

List<List<Integer>> AL; // O(V+E) only using adjacency list
List<Boolean> visited = new ArrayList<>(Collections.nCopies(V, false)); // keep track of visited vertices

void bfs(int s) {
	visited.set(s, true);
	Queue<Integer> q = new LinkedList<>();
	q.add(s); // enqueue the source
	
	while (!q.isEmpty()) {
		int u = q.poll(); // dequeue vertex
		// do something
	
		for (int v : AL.get(u)) // for all neighbouring vertices
			if (!visited.get(v)) {
				visited.set(v, true);
				q.add(v); // enqueue neighbours if not yet visited
			}
	}
}

all the neighbours are enqueued before moving on to the sibling, the queue can grow exponentially on graphs with large branching factor

BFS spanning tree

4-pan: bfs(0)

curr | queue
_    | [ 0 ]
0    | [ 1, 2 ]
1    | [ 2, 3 ]      // 0 was already visited
2    | [ 3, 4 ]      // 0 was already visited
3    | [ 4 ]         // 1, 2 were already visited
4    | [ ]

BFS on disconnected graphs

still
same as DFS

java

List<List<Integer>> al; // O(V+E) only using adjacency list
List<Boolean> visited;  // keep track of visited vertices

void bfs(int u) {
	visited.set(u, true);
	Queue<Integer> q = new LinkedList<>();
	q.add(u); // enqueue the source

	while (!q.isEmpty()) {
		int curr = q.poll(); // dequeue vertex
		// do something

		for (int v : al.get(curr)) // for all neighbouring vertices
			if (!visited.get(v)) {
				visited.set(v, true);
				q.add(v); // enqueue neighbours if not yet visited
			}
	}
}

for (int i = 0; i < visited.length(); i++)
	if (!visited.get(i))
		bfs(i); // if there are any vertices not connected to the first vertex, this will find and call BFS on them

Application

Leetcode: Binary Tree Right Side View

get rightmost node at each level
BFS such that rightmost is last to be visited

java

public List<Integer> rightSideView(TreeNode root) {
	LinkedList<Integer> out = new LinkedList<>();

	Queue<TreeNode> q = new LinkedList<>();
	Queue<Integer> h = new LinkedList<>();
	if (root != null) {
		q.add(root);
		h.add(0);
	}

	while (!q.isEmpty()) {
		TreeNode curr = q.poll();
		int height = h.poll();
		
		// add left first then right, so that right most will be visited last
		if (curr.left != null) {
			q.add(curr.left);
			h.add(height + 1);
		}
		if (curr.right != null) {
			q.add(curr.right);
			h.add(height + 1);
		}

		if (out.size() <= height)
			out.add(curr.val);
		else
			out.set(height, curr.val);
	}

	return out;
}