In this post we'll be discussing depth-first search, a method of traversing a graph. Given a starting node, depth-first search explores as far as possible along each branch before backtracking.
The basic structure of the algorithm is as follows:
function depthFirstSearch(node) {
// base case: if node is null, return
if (node == null) {
return;
}
// mark node as visited
node.visited = true;
// do something with node
// ...
// recurse on each of node's unvisited children
for (let child of node.children) {
if (!child.visited) {
depthFirstSearch(child);
}
}
}
We can see that the depthFirstSearch function takes a node as input. The first thing it does is check if the node is null - if it is, the function simply returns. If the node isn't null, the node is marked as visited, and then the function does something with the node. In our case, we'll simply print out the node.
After that, the function loops through each of the node's unvisited children, and recurses on them.
Here's a simple implementation of depth-first search in JavaScript:
function depthFirstSearch(node) {
if (node == null) {
return;
}
node.visited = true;
console.log(node.value);
for (let child of node.children) {
if (!child.visited) {
depthFirstSearch(child);
}
}
}
And here's an example of how to use it:
// create a graph
// the graph is an array of nodes, each of which has an array of children
let graph = [
{
value: 1,
children: [2, 3, 4]
},
{
value: 2,
children: [5, 6]
},
{
value: 3,
children: [7]
},
{
value: 4,
children: [8, 9]
},
{
value: 5,
children: []
},
{
value: 6,
children: []
},
{
value: 7,
children: []
},
{
value: 8,
children: []
},
{
value: 9,
children: []
}
];
// choose a starting node
let startingNode = graph[0];
// do the search
depthFirstSearch(startingNode);
Running the code above should print out the following:
1
2
5
6
3
7
4
8
9
Try implementing depth-first search yourself with the following exercises:
Here are the answers to the exercises: