Depth-First Search. Graph Algorithms

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

Basic information

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

Choose one of the graph's vertices as the root of the tree.
Recursively explore the edges of each vertex until all vertices reachable from the root (or, in the case of a connected graph, all vertices) have been added to the spanning tree—a tree that contains all the vertices of the graph.

When analyzing graph algorithm runtime, two notations are commonly used:

n = number of vertices, m = number of edges
explicit sizes of vertex and edge sets

For a graph G, the set of vertices is denoted by V(G) (read as "the vertices of G"), and the set of edges by E(G) (read as "the edges of G"). Therefore, n = |V(G)| (read as "the number of vertices in G" or "the cardinality of the vertex set of G") and m = |E(G)|. If G is understood from the context, the sets can simply be referred to as V and E.

Algorithm

Starting from the source vertex, recursively explore one path (branch) to its end
Then move to another path (another branch), and continue

If the search space is too large or infinite, we limit the search depth.

Create a stack to store the visited vertices.
Push the starting vertex onto the stack.
Pop the vertex from the top of the stack and retrieve all of its adjacent vertices.
Ignore any vertices that have already been visited.
Mark all remaining vertices as visited, push them onto the stack, and return to step 3.

pseudocode

1// Input: an arbitrary graph with one vertex chosen as the root.
2// Each vertex has the following properties:
3// distance — initially === 0
4// marked — initially === false
5
6// Output: a spanning tree of the graph.
7
8begin 
9	let stack = [];
10	stack.push(s);
11	while stack.length > 0 do
12		let activeVertex = stack.pop(s);
13		if activeVertex.marked then
14			continue
15		end
16		activeVertex.marked = true;
17		foreach v in Adj[activeVertex] do
18			if v.marked then
19				continue
20			end
21			v.parent =  activeVertex;
22			stack.push(v);
23		end
24	end
25end
26
27// where Adj is the graph represented as an adjacency list,
28// and s is the source vertex.

JavaScript implementation

The following implementation is adapted from an example on this website.

JavaScript

1class Graph {
2	constructor() {
3		this.vertices = {}; // graph adjacency list
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	dfs(startVertex, callback) {
26		let list = this.vertices; // adjacency list
27		let stack = [startVertex]; // stack of vertices to traverse
28        // Use an object to store visited vertices,
29        // as it makes checking whether a property exists easier.
30		let visited = { [startVertex]: 1 }; // visited vertices
31
32		function handleVertex(vertex) {
33			// invoke the callback for the visited vertex
34			callback(vertex);
35
36			// get the list of adjacent vertices
37            // When pushing adjacent vertices onto the stack, use reverse()
38            // to add them in reverse order. This ensures that the branches
39            // are traversed in the same order in which they were originally added.
40			let reversedNeighboursList = [...list[vertex]].reverse();
41
42			reversedNeighboursList.forEach((neighbour) => {
43				if (!visited[neighbour]) {
44					// mark the vertex as visited
45					visited[neighbour] = 1;
46					// push onto the stack
47					stack.push(neighbour);
48				}
49			});
50		}
51
52		// process vertices from the stack until it is empty
53		while (stack.length) {
54			let activeVertex = stack.pop();
55			handleVertex(activeVertex);
56		}
57        // check for disconnected components
58        // If the graph may contain isolated vertices or disconnected subgraphs,
59        // process any unvisited vertices. If not, this section can be omitted.
60		stack = Object.keys(this.vertices);
61
62		while (stack.length) {
63			let activeVertex = stack.pop();
64			if (!visited[activeVertex]) {
65				visited[activeVertex] = 1;
66				handleVertex(activeVertex);
67			}
68		}
69	}
70}

Shortest path problem

Shortest Path Problem: Find a path between two vertices that has the minimum possible weight.

In an unweighted graph: the path with the fewest edges.
In a weighted graph: the path with the smallest total sum of edge weights.

Weighted graphs: Each edge is assigned a weight, which is most commonly a non-negative integer. The weight represents the cost of using that edge.

Variations of the Shortest Path Problem

Single-source shortest path: Find the shortest path from a given source vertex to all other vertices in the graph.
Example: Find the shortest route from a fire station to every location in a city.
Single-destination shortest path: Find the shortest path from every vertex in the graph to a given destination. This is simply the single-source shortest path problem with the direction of all edges reversed.
Example: Find the shortest route to a hospital from any location in the city.
All-pairs shortest path: Find the shortest path between every pair of vertices in the graph.
Example: Ideally, a GPS navigation system should be able to compute the best route from any location to any other location.

Dijkstra’s algorithm

Initialize a set S, initially empty. It will store the vertices whose shortest distances have been finalized.
Insert all vertices of the graph into a priority queue based on their distance from the source vertex s. Initially, the distance to s is 0, while the distance to every other vertex is infinity.
Remove the vertex with the smallest distance from the priority queue (initially s) and relax all of its outgoing edges.
Continue removing the vertex with the smallest distance and relaxing its edges until the priority queue is empty.
At the end of the algorithm, each vertex is assigned the length of its shortest path from the source vertex.

pseudocode

1// Input: Graph G and source vertex s
2// Output: The distance from s to every other vertex in graph G
3// Invariant: S is the set of vertices whose shortest-path distances have been determined
4
5// begin 
6	// Initialize the set of vertices S to the empty set.
7	let S = new Set()
8	// Initialize the priority queue Q and add all vertices of G to it
9	const Q
10	while Q.length > 0 do
11		let activeVertex = Q.ExtractMin();
12		S = S.union(S, {activeVertex})
13		forEach v in Adj(activeVertex) do
14			Relax(activeVertex, v, w)
15		end
16	end
17end
18
19// where Adj is the graph represented as an adjacency list.
20// s is the source vertex.

In this case, "relaxing" an edge means:

Take the priority (current shortest distance) of the current vertex u, add the edge weight w to the new vertex v, and compare the sum with the current priority of v.
If the sum is smaller than the current value of v.d, we have found a shorter path to v, so we replace the old value with the new shorter distance.
Mark u as the new parent of v.

pseudocode

1// Input: Adjacent vertices u and v, and the weight w of the edge between them
2// Output: v.d - the weight of the shortest path found from s to v.
3// If the path goes through the edge from u to v,
4// then the parent of v is assigned the value u
5
6begin 
7	if(v.d > u.d + w(u, v)) then
8		v.d = u.d + w(u,v)
9		v.parent = u
10	end
11end

When a node is removed from the priority queue, we know that we have found the shortest path to this node — any shorter path would have to pass through nodes that have already been processed.

This is a greedy algorithm, but Dijkstra's algorithm is guaranteed to return the optimal solution. Its complexity is O(N²).

"Edge relaxation" takes constant time. For all edges, it takes O(m) in total.

Finding the element with the smallest priority takes O(n) and is performed O(n) times — in total O(N²).

Overall: O(n² + m), where m ≤ n².

Example in JavaScript

The algorithm example is taken from this article..

JavaScript

1function findNearestVertex(distances, visited) {
2	let minDistance = Infinity;
3	let nearestVertex = null;
4
5	Object.keys(distances).forEach((vertex) => {
6		if (!visited[vertex] && distances[vertex] < minDistance) {
7			minDistance = distances[vertex];
8			nearestVertex = vertex;
9		}
10	});
11
12	return nearestVertex;
13}
14
15function dijkstra(graph, startVertex) {
16	let visited = {};
17	let distances = {}; // shortest paths from the starting vertex
18	let previous = {}; // previous vertices
19	let vertices = Object.keys(graph); // list of graph vertices
20
21	// by default, all distances are unknown (infinite)
22	vertices.forEach((vertex) => {
23		distances[vertex] = Infinity;
24		previous[vertex] = null;
25	});
26
27	// the distance to the starting vertex is 0
28	distances[startVertex] = 0;
29
30	function handleVertex(vertex) {
31    	// distance to the vertex
32		let activeVertexDistance = distances[vertex];
33		// adjacent vertices (with their distances)
34		let neighbours = graph[activeVertex];
35		// recalculate distances for all adjacent vertices
36		neighbours.forEach((item) => {
37			const neighbourVertex = item[0];
38			const neighbourWeight = item[1];
39			// current known distance
40			let currentNeighbourDistance = distances[neighbourVertex];
41			// calculated distance
42			let newNeighbourDistance = activeVertexDistance + neighbourWeight;
43			if (newNeighbourDistance < currentNeighbourDistance) {
44				distances[neighbourVertex] = newNeighbourDistance;
45				previous[neighbourVertex] = vertex;
46			}
47		});
48
49		// mark the vertex as visited
50		visited[vertex] = 1;
51	}
52
53    // find the closest unprocessed vertex
54	let activeVertex = findNearestVertex(distances, visited);
55
56	// продолжаем цикл, пока остаются необработанные вершины
57	while (activeVertex) {
58		handleVertex(activeVertex);
59		activeVertex = findNearestVertex(distances, visited);
60	}
61
62	return { distances, previous };
63}

Let's create the following graph and apply the algorithm:

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, weight) {
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, weight]);
19		}
20		if (!this.vertices[vertex2].includes(vertex1)) {
21			this.vertices[vertex2].push([vertex1, weight]);
22		}
23	}
24}
25
26const graph = new Graph();
27
28graph.addVertex("S");
29graph.addVertex("B");
30graph.addVertex("C");
31graph.addVertex("D");
32graph.addVertex("E");
33graph.addVertex("F");
34
35graph.addEdge("S", "B", 14);
36graph.addEdge("S", "D", 24);
37graph.addEdge("B", "C", 8);
38graph.addEdge("B", "F", 4);
39graph.addEdge("B", "E", 86);
40graph.addEdge("C", "D", 55);
41graph.addEdge("C", "F", 1);
42graph.addEdge("D", "E", 7);
43graph.addEdge("F", "E", 13);
44
45console.log(dijkstra(graph.vertices, "S"));
46// {
47//   distances: { S: 0, B: 14, C: 19, D: 24, E: 31, F: 18 },
48//   previous: { S: null, B: 'S', C: 'F', D: 'S', E: 'F', F: 'B' }
49// }