Computer Science Wiki

Graph Breadth-First Search (BFS)

2 min read

Related data structure:

Algorithm Data_Structure Graph BFS

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 ArrayList<>();
	// 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 time. During the process of traversing adjacent vertices in undirected graph, all edges will be visited twice, using time; the over all time complexity is .

Back to parent node: ADT - Graph

Reference:

Graph View

Backlinks