BFS of a Graph Editorial

Practice Problem Link: BFS of a Graph

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a graph compute its BFS. The graph has n nodes indexed 0 to n-1. It is given in the form of an adjacency list. Return the BFS traversal starting at the node indexed 0. Follow the order of nodes as in the adjacency list.

Approach

The approach of BFS is to traverse to the nodes in a level-order manner. All the nodes at the current level get processed before the nodes at the level lower than them. We use a queue to implement BFS. First, we push the source into the queue. We will take the current node at the top of the queue and traverse its adjacency list. If the node is not visited, traverse over them and mark them as visited, and push these nodes into the queue before taking the next element from the top of the queue. Continue the process till the queue is empty and all the nodes are visited.

Analysis

• Time Complexity: O(|V| + |E|)
• Space Complexity: O(|V|)

Implementation

C++

vector<int> bfs(vector<vector<int>> adjList) {
    queue<int> queue;
	vector<int> traversal;
	vector<bool> isVisited (adjList.size(), false);
	if(adjList.size() == 0) {
		return traversal;
	}
	queue.push(0);
	isVisited[0] = true;
	for(int i = 0; i < adjList.size(); i++) {
		int node = queue.front();
		queue.pop();
		traversal.push_back(node);
		for(int j = 0; j < adjList[node].size(); j++) {
			if(isVisited[adjList[node][j]]) {
				continue;
			}
			queue.push(adjList[node][j]);
			isVisited[adjList[node][j]] = true;
		}
	}
	return traversal;
}

Java

class Solution {
    ArrayList<Integer> bfs(ArrayList<Integer>[] adjList) {
        Queue<Integer> queue = new LinkedList<Integer>();
		ArrayList<Integer> traversal = new ArrayList<Integer>();
		boolean[] isVisited = new boolean[adjList.length];
		if(adjList.length == 0) {
			return traversal;
		}
		queue.add(0);
		isVisited[0] = true;
		for(int i = 0; i < adjList.length; i++) {
			int node = queue.poll();
			traversal.add(node);
			for(int j = 0; j < adjList[node].size(); j++) {
				if(isVisited[adjList[node].get(j)]) {
					continue;
				}
				queue.add(adjList[node].get(j));
				isVisited[adjList[node].get(j)] = true;
			}
		}
		return traversal;
    }
}