Breath First Search

Travels the graph by levels, that is, visit every node at level n before going to level n + 1

Algorithm

$O(V+E)$

1. Initialization: Enqueue the starting node into a queue and mark it as visited.
2. Exploration: While the queue is not empty:
   • Dequeue a node from the queue and visit it (e.g., print its value).
   • For each unvisited neighbor of the dequeued node:
     • Enqueue the neighbor into the queue.
     • Mark the neighbor as visited.
3. Termination: Repeat step 2 until the queue is empty.

C++ code

vector<T> Graph<T>::bfs(const T &source) const {
	// Create empty queue and set all vertices as unvisited
	vector<T> res;
	queue<Vertex<T>*> tempQueue;
	for (Vertex<T>* i: getVertexSet()) {
		i->setVisited(false);
	}
	Vertex<T>* initialVertex = findVertex(source);
	if (initialVertex == NULL) {
		return res;
	}
	tempQueue.push(initialVertex);
	initialVertex->setVisited(true);
	// Visit all nodes and add their neighbors to the queue
	while (!tempQueue.empty()){
		Vertex<T>* currentVertex = tempQueue.front();
		tempQueue.pop();
		res.push_back(currentVertex->getInfo());
		for (Edge<T> edge : currentVertex->getAdj()){
			if (!edge.getDest()->isVisited()){
				edge.getDest()->setVisited(true);
				tempQueue.push(edge.getDest());
			}
		}
	}
	return res;
}