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 {
private Map<String, List<String>> adjacencyList = new HashMap<>();
public void addVertex(String vertex) {
adjacencyList.putIfAbsent(vertex, new ArrayList<>());
}
public void addEdge(String v1, String v2) {
adjacencyList.get(v1).add(v2);
adjacencyList.get(v2).add(v1);
}
}
public List<String> depthFirstIterative(String start) {
Stack<String> stack = new Stack<>();
List<String> result = new ArrayList<>();
Set<String> visited = new HashSet<>();
stack.push(start);
visited.add(start);
while (!stack.isEmpty()) {
String currentVertex = stack.pop();
result.add(currentVertex);
for (String neighbor : adjacencyList.get(currentVertex)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
stack.push(neighbor);
}
}
}
return result;
}
public List<String> depthFirstRecursive(String start) {
List<String> result = new ArrayList<>();
Set<String> visited = new HashSet<>();
Map<String, List<String>> adj = adjacencyList;
dfs(start, visited, result, adj);
return result;
}
private void dfs(String vertex, Set<String> visited, List<String> result, Map<String, List<String>> adj) {
if (vertex == null) return;
visited.add(vertex);
result.add(vertex);
for (String neighbor : adj.get(vertex)) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited, result, adj);
}
}
}
// 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: