Graphs 101: Let’s BFS and DFS.

In this article we will dive into graph basics.

The 2 most common used representation of graphs are the adjacency list and adjacency matrix.

Adjacency list

	adjacencyList = {
		1: [2, 4],
		2: [1, 3],
		3: [2, 4],
		4: [1, 3]
	}

Graph Traversals

There are two graph traversals: breadth first search and depth first search.

BFS visits the nodes one level at a time. To prevent visiting the same node more than once, we’ll maintain a visited object.

For BFS we utilize a Queue to process the nodes in a First In First Out fashion. The time complexity is O(v+e).

Pseudocode

/*
	pcode:
	- create result array variable
	- create a queue variable
	- create a visited map
	- add the starting vertex to the queue & visited map
	- while queue is not empty:
	  - dequeue current vertex
	  - push current vertex to result array
	  - loop thru current vertex adjacency list:
	    - for each adjacent vertex, if vertex is unvisited:
	    	- add vertex to visited map
	    	- enqueue vertex
	- return result array
*/

Code

// code:
function bfs(node) {
	const result = [];
	const queue = [node];
	const visited = {};
	visited[start] = true;

	while (queue.length) {
		let currVertex = queue.pop();
		result.push(currVertex);

		adjacencyList[currVertex].forEach(edges => {
			if (!visited[edges]) {
				visited[edges] = true;
				queue.unshift(edges);
			}
		});
	}
	return results;
}

DFS visits the nodes depth wise so we will use a Stack in order to process Last In First Out fashion.

Starting from a vertex, we’ll push the neighboring vertices to our stack. Whenever a vertex is popped, it is marked visited in our visited object. Its neighboring vertices are pushed to the stack. Since we are always popping a new adjacent vertex, our algorithm will always explore a new level.

We can also use the intrinsic stack calls to implement DFS recursively.

The time complexity is the same as BFS, O(v+e).

Pseudocode

/*
	pcode:
	- create a stack array
	- create a result array
	- create a visited map
	- push the starting vertex to the stack & visited map
	- while the stack is not empty:
		- pop and store the vertex
		- push current vertex to result array
		- loop thru current vertex adjacency list:
			- for each adjacent vertex, if vertex is unvisited:
				- add vertex to visited map
				- push vertex to stack
	- return result array
*/

Code

// code:
function dfsRecursively(node) {
	const result = [];
	const visited = {};

	function dfs(vertex) {
		// base case
		if (!vertex) return null;

		// set visited
		visited[vertex] = true;
		result.push(vertex);

		// recursive action
		adjacencyList[vertex].forEach(edge => {
			if (!visited[edge]) {
				return dfs(edge);
			}
		});
	}

	dfs(node);

	return result;
}

function dfsIterative(node) {
	const result = [];
	const stack = [node];
	const visited = {};
	visited[start] = true;

	while (stack.length) {
		let currVertex = stack.pop();
		result.push(currVertex);

		adjacencyList[currVertex].forEach(edge => {
			if (!visited[edge]) {
				visited[edge] = true;
				stack.push(edge);
			}
		});
	}

	return result;
}

There it is, now let’s see how to use this to solve problems.