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 (Java)
class Graph {
private Map<String, List<String>> adjacencyList = new HashMap<>();
public void addVertex(String vertex) {
adjacencyList.putIfAbsent(vertex, new ArrayList<>());
}
public void addEdge(String vertex1, String vertex2) {
adjacencyList.get(vertex1).add(vertex2);
// For undirected graph, add the reverse edge too
// adjacencyList.get(vertex2).add(vertex1);
}
}
Recursive DFT Implementation
The recursive approach to DFT leverages the call stack to keep track of vertices to
visit:
// Recursive DFT implementation (Java)
class Graph {
private Map<String, List<String>> adjacencyList = new HashMap<>();
// ... addVertex and addEdge methods ...
public List<String> depthFirstTraversalRecursive(String startVertex) {
List<String> result = new ArrayList<>();
Set<String> visited = new HashSet<>();
dfs(startVertex, visited, result);
return result;
}
private void dfs(String vertex, Set<String> visited, List<String> result) {
if (vertex == null || visited.contains(vertex)) return;
visited.add(vertex);
result.add(vertex);
for (String neighbor : adjacencyList.getOrDefault(vertex, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited, result);
}
}
}
}
// Example usage
Graph 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");
System.out.println(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 (Java)
class Graph {
private Map<String, List<String>> adjacencyList = new HashMap<>();
// ... addVertex and addEdge methods ...
public List<String> depthFirstTraversalIterative(String startVertex) {
List<String> result = new ArrayList<>();
Set<String> visited = new HashSet<>();
Deque<String> stack = new ArrayDeque<>();
stack.push(startVertex);
while (!stack.isEmpty()) {
String current = stack.pop();
if (!visited.contains(current)) {
visited.add(current);
result.add(current);
for (String neighbor : adjacencyList.getOrDefault(current, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
return result;
}
}
// Example usage
// System.out.println(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