Breadth-First Search. Graph Algorithms

This is a short expanded summary of the section on breadth-first search in the book Computer Science Guide by William Springer.

Basic Information

The Breadth-First Search algorithm (BFS) transforms an arbitrary graph into a search tree.

Choose one of the vertices of the graph as the root of the tree.
Recursively explore the edges of each vertex until all vertices of the graph are added to the spanning tree (a tree that contains all vertices of the graph).
(More precisely: all vertices that can be reached by following edges from the root; in the case of a connected graph, this will be all vertices.)

When analyzing the runtime of graph algorithms, two notation systems are commonly used:

Use n to represent the number of vertices and m to represent the number of edges.
Specify the sizes of the vertex and edge sets.

For example, for graph G, the set of vertices is denoted as V(G) (read as "vertices of G"), and the set of edges is denoted as E(G) (read as "edges of G"). Therefore:

n = |V(G)| (can be read as "the size of the vertex set of G")
m = |E(G)| (the size of the edge set of G)

If G is implied by default, the sets can simply be referred to as V and E.

Algorithm:

Explore all vertices adjacent to the root (at distance k from the root). The root itself is denoted as s (source).
Explore all vertices adjacent to the root's neighbors that have not yet been explored (at distance k + 1), and so on.

When the algorithm is complete, the depth of each node in the tree is the minimum number of edges (the length of the shortest path) required to reach that node from s, both in the search tree and in the original graph.

To find this path, follow the pointers to the parent nodes until the node s is reached.

Time complexity — O(n + m).

Initializing the three properties (mentioned above) takes constant time for each vertex. In total — O(n).
Each vertex is added to the queue, removed from the queue, and each of the properties is updated no more than once. Each operation takes O(1) time, giving a total of O(n).
We iterate through all neighbors of each vertex to check whether they have been visited — O(m).

Space complexity — O(n + m).

Storing the graph requires O(n + m) memory.
The queue requires O(n) memory.

Overall, BFS runs in linear time with respect to the size of the input data.

pseudocode

1// Input: An arbitrary graph with one vertex chosen as the root. All vertices
2// have the following properties:
3//
4// distance - initially === Infinity
5// parent - initially === null
6// marked - initially === false
7//
8// Output: A spanning tree of the graph in which each vertex is as close to
9// the root as possible.
10
11begin 
12	let queue = [];
13	s.distance = 0;
14	s.marked = true;
15	queue.push(s);
16	while q.length > 0 do
17		let activeVertex = queue.shift();
18		foreach v in Adj[activeVertex] do
19			if v.marked then
20				continue
21			end
22			v.parent =  activeVertex;
23			v.distance = activeVertex.distance + 1
24			v.marked = true
25			queue.push(v)
26		end
27	end
28end
29
30// where Adj is the graph represented as an adjacency list.

JavaScript Implementation

Both examples are taken from this website.

Example of f a graph implementation.

JavaScript

1class Graph {
2	constructor() {
3		this.vertices = {}; // adjacency list of the graph
4	}
5
6	addVertex(value) {
7		if (!this.vertices[value]) {
8			this.vertices[value] = [];
9		}
10	}
11
12	addEdge(vertex1, vertex2) {
13		if (!(vertex1 in this.vertices) || !(vertex2 in this.vertices)) {
14			throw new Error("There are no such vertices in the graph.");
15		}
16
17		if (!this.vertices[vertex1].includes(vertex2)) {
18			this.vertices[vertex1].push(vertex2);
19		}
20		if (!this.vertices[vertex2].includes(vertex1)) {
21			this.vertices[vertex2].push(vertex1);
22		}
23	}
24
25	bfs(startVertex, callback) {
26		let list = this.vertices; // adjacency list
27		let queue = [startVertex]; // queue of vertices to be processed
28		let visited = { [startVertex]: 1 }; // visited vertices
29      
30		function handleVertex(vertex) {
31			// call the callback function for the visited vertex
32			callback(vertex);
33
34			// get the list of adjacent vertices
35			let neighboursList = list[vertex];
36
37			neighboursList.forEach((neighbour) => {
38				if (!visited[neighbour]) {
39					visited[neighbour] = 1;
40					queue.push(neighbour);
41				}
42			});
43		}
44
45		// process the vertices in the queue until it is empty
46		while (queue.length) {
47			let activeVertex = queue.shift();
48			handleVertex(activeVertex);
49		}
50
51		queue = Object.keys(this.vertices);
52
53		// Repeat the process for the remaining unvisited vertices
54		while (queue.length) {
55			let activeVertex = queue.shift();
56			if (!visited[activeVertex]) {
57				visited[activeVertex] = 1;
58				handleVertex(activeVertex);
59			}
60		}
61	}
62}
63
64const graph = new Graph();
65
66graph.addVertex("A");
67graph.addVertex("B");
68graph.addVertex("C");
69graph.addVertex("D");
70graph.addVertex("E");
71graph.addVertex("F");
72graph.addVertex("G");
73graph.addVertex("H");
74
75graph.addEdge("A", "B");
76graph.addEdge("A", "C");
77graph.addEdge("C", "D");
78graph.addEdge("C", "E");
79graph.addEdge("A", "F");
80graph.addEdge("F", "G");
81
82graph.bfs('A', v => console.log(v));
83
84// A
85// B
86// C
87// F
88// D
89// E
90// G
91// H

Example of a tree implementation.

JavaScript

1// Let's use a simple queue implementation.
2class Queue {
3	constructor() {
4		this.arr = [];
5	}
6	enqueue(value) {
7		this.arr.push(value);
8	}
9	dequeue() {
10		return this.arr.shift();
11	}
12	isEmpty() {
13		return this.arr.length == 0;
14	}
15}
16
17class BinaryTreeNode {
18	constructor(value) {
19		this.left = null;
20		this.right = null;
21		this.parent = null;
22		this.value = value;
23	}
24
25	get height() {
26		let leftHeight = this.left ? this.left.height + 1 : 0;
27		let rightHeight = this.right ? this.right.height + 1 : 0;
28		return Math.max(leftHeight, rightHeight);
29	}
30
31	// When inserting a node, it is important to update all affected references:
32// the parent's left or right pointer and the child's parent pointer.
33// If the parent already had a child, that child's parent property must be set to null.
34
35	setLeft(node) {
36		if (this.left) {
37			this.left.parent = null;
38		}
39		if (node) {
40			this.left = node;
41			this.left.parent = this;
42		}
43	}
44
45	setRight(node) {
46		if (this.right) {
47			this.right.parent = null;
48		}
49		if (node) {
50			this.right = node;
51			this.right.parent = this;
52		}
53	}
54}
55
56function traverseBF(root, callback) {
57	let nodeQueue = new Queue();
58	nodeQueue.enqueue(root);
59
60	while (!nodeQueue.isEmpty()) {
61		let currentNode = nodeQueue.dequeue();
62
63		// Call the callback function for the current node.
64		callback(currentNode);
65
66		// Add the left child to the queue.
67		if (currentNode.left) {
68			nodeQueue.enqueue(currentNode.left);
69		}
70
71		// Add the right child to the queue.
72		if (currentNode.right) {
73			nodeQueue.enqueue(currentNode.right);
74		}
75	}
76}
77
78let aNode = new BinaryTreeNode('a');
79
80let bNode = new BinaryTreeNode('b');
81aNode.setLeft(bNode);
82
83let cNode = new BinaryTreeNode('c');
84aNode.setRight(cNode);
85
86let dNode = new BinaryTreeNode('d');
87bNode.setRight(dNode);
88
89let eNode = new BinaryTreeNode('e');
90cNode.setLeft(eNode);
91
92let fNode = new BinaryTreeNode('f');
93cNode.setRight(fNode);
94
95traverseBF(aNode, (node) => console.log(node.value));
96
97// a
98// b
99// c
100// d
101// e
102// f

Applications of Breadth-First Search

BFS is useful for any problem that requires finding shortest paths.

It finds the length of the shortest path from the source vertex s to any other vertex in the graph in linear time.
It can also reconstruct the shortest path by following the parent pointers from the target vertex back to the root, in time proportional to the length of the path.

Examples of Applications

Navigation Systems

Route planning with GPS.

If a mapping system stores data about a local area as a graph, where the vertices represent addresses (or intersections) and the edges represent streets (or, more precisely, short road segments), it can use Breadth-First Search to build a search tree with your current location as the source.

Checking Whether a Graph Is Bipartite

A graph is not bipartite if there is an edge connecting the current vertex to an already visited vertex whose distance is either the same or differs by an even number (i.e., the two vertices would be assigned the same color).

Another indication that a graph is not bipartite is the presence of an odd cycle. Such a cycle consists of an edge together with one or more paths to the lowest common ancestor of the two vertices connected by that edge.

A bipartite graph (or bigraph) is a graph whose set of vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other. In other words, there are no edges between vertices within the same set.

Bipartite graphs are used in:

Coding theory, which studies topics such as cryptography, data compression, and error correction.
Petri nets, which are used to model the behavior of systems.
Social network analysis.
Cloud computing.