Write a function that implements the depth-first search algorithm on a directed graph (in adjacency list format), given a starting node.
const graph1 = {A: ['B', 'C', 'D'],B: ['E', 'F'],C: ['G', 'H'],D: ['I', 'J'],E: ['D'],F: [],G: [],H: [],I: [],J: [],};depthFirstSearch(graph1, 'A'); // ['A', 'B', 'E', 'D', 'I', 'J', 'F', 'C', 'G', 'H']depthFirstSearch(graph1, 'B'); // ['B', 'E', 'D', 'I', 'J', 'F']const graph2 = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F', 'G'],'D': [],'E': [],'F': [],'G': [],};depthFirstSearch(graph2, 'A')); // ['A', 'B', 'D', 'E', 'C', 'F', 'G']depthFirstSearch(graph2, 'E')); // ['E']
Depth-first search (DFS) is an algorithm used for traversing a graph or a tree. The output from DFS is an array of the graph's nodes in the order they were traversed. This output is useful for a variety of different use cases and purposes, which makes DFS a useful algorithm to know. Some use cases:
Here is an overview of how DFS works to traverse a graph, using the standard implementation that takes in an adjacency list (we use an array instead) and the root node:
If unspecified:
The solution implements the algorithm outlined in the description.
/*** @param {Record<string, Array<string>} graph The adjacency list representing the graph.* @param {string} source The source node to start traversal from. Has to be a valid node if graph is non-empty.* @return {string[]} A DFS-traversed order of nodes.*/export default function depthFirstSearch(graph, source) {// If there are no nodes in the graph, just return an empty arrayif (Object.keys(graph).length === 0) {return [];}// Create an stack to store the nodes to be visited. We can simulate// stacks using arrays in JavaScript.// Add the root node since we're doing a pre-order DFS.const toBeVisited = [];toBeVisited.push(source);// Initialize a set that tracks visited nodes.const visited = new Set();// Loop as long as array is empty (i.e. there are still nodes to be visited).while (toBeVisited.length !== 0) {// Pop top node from array (toBeVisited) and add it to the set (visited).const node = toBeVisited.pop();visited.add(node);// Retrieve neighbors (values of the adjacency list input Object)const neighbors = graph[node];// Push neighbors, in reverse order, onto array to be visited// to preserve original order of neighbors when visiting (popping off the array).for (let i = neighbors.length - 1; i >= 0; i--) {const neighbor = neighbors[i];// First check if the neighbor has already been visited before adding it.if (!visited.has(neighbor)) {toBeVisited.push(neighbor);}}}// The visited nodes is the traversal order.return Array.from(visited);}
We can also perform DFS recursively, which is can be more intuitive in certain cases. The recursion call stack is an implicit stack to track which nodes to visit next.
/*** @param {Object} graph Node to array of neighboring nodes.* @param {string} source Source node to start traversal from. Has to be a valid node if graph is non-empty.* @return {string[]} A DFS-traversed order of nodes.*/export default function depthFirstSearch(graph, source) {// If there are no nodes in the graph, just return an empty arrayif (Object.keys(graph).length === 0) {return [];}// Initialize a set that tracks visited nodes.const visited = new Set();function traverse(node) {// Visited before, we can ignore.if (visited.has(node)) {return;}visited.add(node);// Recursively visit each neighbor.graph[node].forEach((neighbor) => {traverse(neighbor);});}// Start traversing from the source.traverse(source);// The visited nodes is the traversal order.return Array.from(visited);}
import depthFirstSearch from './depth-first-search';describe('depthFirstSearch', () => {test('empty graph', () => {expect(depthFirstSearch({}, 'A')).toEqual([]);});test('graphs with one node', () => {expect(depthFirstSearch({ A: [] }, 'A')).toEqual(['A']);});test('graphs with two nodes', () => {expect(depthFirstSearch({ A: ['B'], B: [] }, 'A')).toEqual(['A', 'B']);expect(depthFirstSearch({ A: ['A', 'B'], B: [] }, 'A')).toEqual(['A', 'B']);expect(depthFirstSearch({ A: ['A', 'B'], B: [] }, 'B')).toEqual(['B']);expect(depthFirstSearch({ A: ['A', 'B'], B: ['A'] }, 'B')).toEqual(['B','A',]);});test('graphs with multiple nodes', () => {expect(depthFirstSearch({ A: ['B'], B: ['C'], C: [] }, 'A')).toEqual(['A','B','C',]);expect(depthFirstSearch({ A: ['B', 'C'], B: [], C: [] }, 'A')).toEqual(['A','B','C',]);expect(depthFirstSearch({ A: ['B', 'C'], B: [], C: [], D: ['B'], E: ['C'] },'A',),).toEqual(['A', 'B', 'C']);expect(depthFirstSearch({ A: ['D', 'E'], B: [], C: [], D: ['B'], E: ['C'] },'A',),).toEqual(['A', 'D', 'B', 'E', 'C']);expect(depthFirstSearch({A: ['D', 'E'],B: ['A', 'B', 'C', 'D', 'E'],C: [],D: ['B'],E: ['C'],},'A',),).toEqual(['A', 'D', 'B', 'C', 'E']);expect(depthFirstSearch({A: ['A', 'B', 'C', 'D', 'E'],B: [],C: [],D: ['B'],E: ['C'],},'A',),).toEqual(['A', 'B', 'C', 'D', 'E']);// Graph taken from https://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/const graph = {A: ['B', 'C'],B: ['A', 'D', 'E'],C: ['A', 'E'],D: ['B', 'E', 'F'],E: ['B', 'C', 'D', 'F'],F: ['D', 'E'],};expect(depthFirstSearch(graph, 'A')).toEqual(['A','B','D','E','C','F',]);expect(depthFirstSearch(graph, 'B')).toEqual(['B','A','C','E','D','F',]);expect(depthFirstSearch(graph, 'C')).toEqual(['C','A','B','D','E','F',]);expect(depthFirstSearch(graph, 'D')).toEqual(['D','B','A','C','E','F',]);expect(depthFirstSearch(graph, 'E')).toEqual(['E','B','A','C','D','F',]);expect(depthFirstSearch(graph, 'F')).toEqual(['F','D','B','A','C','E',]);});test('disjoint graphs', () => {expect(depthFirstSearch({ A: ['B'], B: [], C: [], D: ['C'] }, 'A')).toEqual(['A', 'B'],);expect(depthFirstSearch({ A: ['B'], B: [], C: [], D: ['C'] }, 'C')).toEqual(['C'],);expect(depthFirstSearch({ A: ['B'], B: [], C: [], D: ['C'] }, 'D')).toEqual(['D', 'C'],);});test('cyclic graphs', () => {expect(depthFirstSearch({ A: ['A'] }, 'A')).toEqual(['A']);expect(depthFirstSearch({A: ['B', 'C', 'D'],B: ['E', 'F'],C: ['G', 'H'],D: ['I', 'J'],E: ['D'],F: [],G: [],H: [],I: [],J: [],},'A',),).toEqual(['A', 'B', 'E', 'D', 'I', 'J', 'F', 'C', 'G', 'H']);expect(depthFirstSearch({A: ['B', 'C', 'D'],B: ['E', 'F'],C: ['G', 'H'],D: ['I', 'J'],E: ['D'],F: [],G: [],H: [],I: [],J: [],},'B',),).toEqual(['B', 'E', 'D', 'I', 'J', 'F']);expect(depthFirstSearch({A: ['B', 'C'],B: ['D', 'E'],C: ['F', 'G'],D: [],E: [],F: [],G: [],},'A',),).toEqual(['A', 'B', 'D', 'E', 'C', 'F', 'G']);expect(depthFirstSearch({A: ['B', 'C'],B: ['D', 'E'],C: ['F', 'G'],D: [],E: [],F: [],G: [],},'E',),).toEqual(['E']);});});
console.log()
statements will appear here.