Graph Breadth-First Search (BFS)

Related data structure:

• ADT - Graph

AlgorithmData_StructureGraphBFS

---

Breadth-First Search (BFS) is a near-to-far traversal method, starting from a certain node, always prioritising the visit to the nearest vertices and expanding outwards layer by layer.

Implementation

BFS is usually implemented with the help of a queue, the queue has first-in-first-out property.

1. Add the starting vertex to the queue and start the loop
2. In each iteration of the loop, pop the vertex at the front of the queue and record it as visited, then add all adjacent vertices of that vertex to the back of the queue
3. Repeat step 2 until all vertices have been visited

List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) {
	// BFS ordered list
	List<Vertex> res = new ArrayListM<>();
	// record visited vertices
	Set<Vertex> visited = new HashSet<>();
	visited.add(startVet);
	// queue for BFS
	Queue<Vertex> que = new LinkedList<>();
	// start from the starting vertex
	que.offer(startVet);
	// start from startVet, loop until all vertices are visited
	while (!que.isEmpty()) {
		Vertex vet = que.poll(); // first out
		res.add(vet); 
		for (Vertex adjVet : graph.ajdList.get(vet)) {
			if (visited.contains(adjVet))
				continue; // skip visited vertex
			que.offer(adjVet); // enqueue unvisited vertex
			visited.add(adjVet);
		}
	}
	return res;
}

Time complexity

All vertices will be queued and dequeued once, using $O(|V|)$ time. During the process of traversing adjacent vertices in undirected graph, all edges will be visited twice, using $O(|E|)$ time; the over all time complexity is $O(|V|+|E|)$.

---

Back to parent node: ADT - Graph

Reference:

• https://www.hello-algo.com/en/chapter_graph/graph_traversal/#1-algorithm-implementation