Learn how to implement depth-first search without recursion using a stack data structure. Master this essential technique for traversing graphs in a memory-efficient way.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
}
depthFirstIterative(start) {
const stack = [start];
const result = [];
const visited = {};
visited[start] = true;
while (stack.length) {
const currentVertex = stack.pop();
result.push(currentVertex);
// Visit all unvisited neighbors
this.adjacencyList[currentVertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return result;
}
depthFirstRecursive(start) {
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
function dfs(vertex) {
if (!vertex) return;
visited[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach(neighbor => {
if (!visited[neighbor]) {
dfs(neighbor);
}
});
}
dfs(start);
return result;
}
// Create a graph
const g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");
g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "E");
g.addEdge("D", "E");
g.addEdge("D", "F");
g.addEdge("E", "F");
// The graph looks like:
// A
// / \
// B C
// | |
// D---E
// \ /
// F
console.log(g.depthFirstIterative("A")); // ["A", "C", "E", "F", "D", "B"]
Implement a function that finds a path between two vertices in a graph using iterative DFS.
findPathDFS(start, end) to the Graph classclass Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
// Implement your solution here
findPathDFS(start, end) {
// Your code here
}
}
// Create a test graph
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.addEdge("D", "E");
graph.addEdge("D", "F");
graph.addEdge("E", "F");
console.log(graph.findPathDFS("A", "F")); // Should return a valid path, e.g., ["A", "B", "D", "F"]
console.log(graph.findPathDFS("A", "G")); // Should return []
After completing this challenge, try these extensions: