Depth-First Search | Skilled.dev
Learn

# Depth-First Search

## Course launching November 17, 2020

Credit: VisuAlgo
Pros ðŸ”¥
• Less memory used
Paths tend to contain less nodes, so it will be better with memory (good if tree is wider than it is deep)
• Determine if a path exists
It is efficient in finding if a path between a source and target exists
Cons ðŸ¤•
• Deep graphs are slow
It can get slow if the graph is deep and doesn't traverse a node's closest neighbors quickly (bad if tree is deeper than it is wide)

Depth-first search (DFS) follows paths to their end before moving on to the next path. It goes deep before it goes wide.

To implement DFS, we use a stack data structure. With recursive DFS, our stack is just the function call stack, but if we do it iteratively, we create an actual stack data structure in our code. A stack is used because we continue to add items to it until we reach the end of a path. Then we pop them off until we return to the beginning of the path and perform the operation again.

DFS is often assumed to require less memory than BFS because the width of a path tends to have more nodes than its height. DFS only stores a path whereas BFS must store all of a node's children. Because of this assumption on less memory, DFS is typically the preferred choice.

To implement DFS, we will use a graph node that stores `data` and its `edges`. The `edges` variable is just an array of pointers to its sibling nodes. We will also assume our graph is undirected.

Nodes will take the following form:

``````class GraphNode {
constructor(data) {
this.data = data;
this.edges = [];
}
}
``````

Because there can be cycles in graphs or multiple nodes that share an edge, we need to track if we have visited a given item. If not, we could traverse our graph infinitely.

The iterative DFS is give below:

``````const iterativeDepthFirstSearch = (startingNode) => {
// Init our stack and set of visited nodes
const dfsStack = [startingNode];
const visitedNodes = new Set();

while (dfsStack.length > 0) {
const node = dfsStack.pop();

visit(node);

node.edges.forEach(childNode => {
if (!visitedNodes.has(childNode)) {
dfsStack.push(childNode);
}
});
}
};
``````

In the iterative solution, we maintain our stack and track if have visited a node. My using a stack, we are always traversing from the most recently added item which keeps us moving towards the end of any given path.

The recursive DFS solution is below. In this case, the stack used to store nodes is actually the calls stack.

``````// Create a helper function to add visitedNodes to the signature
const dfs = (currentNode, visitedNodes) => {
// Use node value for the question
visit(currentNode);

currentNode.edges.forEach(childNode => {
if (!visitedNodes.has(childNode)) {
dfs(childNode, visitedNodes);
}
});
}

const recursiveDepthFirstSearch = startingNode => {
// Init our stack and set of visited nodes
const visitedNodes = new Set();
dfs(startingNode, visitedNodes);
};
``````
Prev
Graphs
Next