g #2
Description
// dfs_stacked.go
// Iterative Depth-First Search (DFS) using an explicit stack.
// Non-recursive version — perfect for deep graphs/trees where recursion would hit stack overflow.
// Works on directed or undirected graphs (just build the adj list accordingly).
package main
import "fmt"
// Graph is represented as adjacency list: graph[i] = list of neighbors of node i
type Graph [][]int
// DFSIterative returns the order of nodes in which they are first visited (discovery order).
// Matches the order of a recursive DFS when neighbors are pushed in reverse.
func DFSIterative(graph Graph, start int) []int {
n := len(graph)
if n == 0 {
return nil
}
visited := make([]bool, n)
stack := make([]int, 0, n) // explicit stack (pre-allocate for efficiency)
order := make([]int, 0, n) // discovery order
stack = append(stack, start)
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1] // pop
if visited[node] {
continue
}
visited[node] = true
order = append(order, node)
// Push neighbors in reverse order → simulates recursive call stack exactly
for i := len(graph[node]) - 1; i >= 0; i-- {
nei := graph[node][i]
if !visited[nei] {
stack = append(stack, nei)
}
}
}
return order
}
// Example usage
func main() {
// Graph with 6 nodes (0..5)
// 0 → 1, 2
// 1 → 3, 4
// 2 → 5
graph := Graph{
0: {1, 2},
1: {3, 4},
2: {5},
3: {},
4: {},
5: {},
}
fmt.Println("DFS discovery order starting from 0:")
fmt.Println(DFSIterative(graph, 0)) // Expected: [0 2 5 1 4 3] or similar (order of children affects exact sequence)
}