Module 4: Graphs IV
Advanced graph traversal techniques with depth-first traversal
Understanding Depth-First Traversal
Depth-First Traversal (DFT) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses the principle of recursion and backtracking or a stack data structure for its implementation.
Key Characteristics of DFT:
- Explores deeply into the graph before backtracking
- Uses a stack data structure (either explicitly or via recursion)
- Visits all nodes connected from a starting node
- Can detect cycles when implemented with proper tracking
- Often simpler to implement than breadth-first traversal for recursive problems
Graph Representation
Before implementing DFT, we need a way to represent our graph. Common representations include:
// Adjacency List representation
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
// For undirected graph, add the reverse edge too
// this.adjacencyList[vertex2].push(vertex1);
}
}
Recursive DFT Implementation
The recursive approach to DFT leverages the call stack to keep track of vertices to visit:
// Recursive DFT implementation
class Graph {
// ... previous methods from above ...
depthFirstTraversalRecursive(startVertex) {
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
// Helper function to conduct DFT recursively
function dfs(vertex) {
if (!vertex) return null;
// Mark vertex as visited
visited[vertex] = true;
// Add vertex to result
result.push(vertex);
// Visit each neighbor
adjacencyList[vertex].forEach(neighbor => {
if (!visited[neighbor]) {
return dfs(neighbor);
}
});
}
// Start DFT from startVertex
dfs(startVertex);
return result;
}
}
// Example usage
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");
console.log(g.depthFirstTraversalRecursive("A")); // ["A", "B", "D", "E", "F", "C"]
Iterative DFT Implementation
The iterative approach uses an explicit stack to keep track of vertices to visit:
// Iterative DFT implementation
class Graph {
// ... previous methods ...
depthFirstTraversalIterative(startVertex) {
const stack = [startVertex];
const result = [];
const visited = {};
visited[startVertex] = true;
while (stack.length) {
const currentVertex = stack.pop();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return result;
}
}
// Example usage
console.log(g.depthFirstTraversalIterative("A")); // May produce different order than recursive version
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges
Space Complexity: O(V) for the visited set and stack/recursion call stack