Implementing Depth-First Search in Go

👋 Welcome Gophers! In this lesson, we are going to be implementing the Depth-First Search algorithm that we looked at in the previous lesson.

Implementation

Let’s start off by creating a new file called main.go within a new directory called 06-dfs/. We’ll build a graph implementation and then implement DFS on it.

First, let’s define our Graph struct using an adjacency list representation:

package main

import "fmt"

// Graph represents an undirected graph using adjacency list
type Graph struct {
	vertices int
	edges    map[int][]int
}

// NewGraph creates a new graph with given number of vertices
func NewGraph(vertices int) *Graph {
	return &Graph{
		vertices: vertices,
		edges:    make(map[int][]int),
	}
}

// AddEdge adds an undirected edge between two vertices
func (g *Graph) AddEdge(u, v int) {
	g.edges[u] = append(g.edges[u], v)
	g.edges[v] = append(g.edges[v], u)
}

Now let’s implement the recursive DFS function:

// DFS performs a depth-first search starting from a given vertex
func (g *Graph) DFS(start int) []int {
	visited := make(map[int]bool)
	var result []int

	g.dfsHelper(start, visited, &result)

	return result
}

// dfsHelper is a recursive helper function for DFS
func (g *Graph) dfsHelper(vertex int, visited map[int]bool, result *[]int) {
	// Mark the current vertex as visited
	visited[vertex] = true
	*result = append(*result, vertex)
	fmt.Printf("Visiting vertex %d\n", vertex)

	// Recursively visit all unvisited neighbors
	for _, neighbor := range g.edges[vertex] {
		if !visited[neighbor] {
			g.dfsHelper(neighbor, visited, result)
		}
	}
}

Great! Now let’s create a main function to test our implementation:

func main() {
	fmt.Println("Depth-First Search Algorithm in Go")

	// Create a graph with 6 vertices
	g := NewGraph(6)

	// Add edges to create our graph
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	g.AddEdge(3, 5)
	g.AddEdge(4, 5)

	fmt.Println("\nDFS traversal starting from vertex 0:")
	result := g.DFS(0)
	fmt.Printf("Traversal order: %v\n", result)
}

Let’s run this and see what happens:

$ go run main.go
Depth-First Search Algorithm in Go

DFS traversal starting from vertex 0:
Visiting vertex 0
Visiting vertex 1
Visiting vertex 3
Visiting vertex 5
Visiting vertex 4
Visiting vertex 2
Traversal order: [0 1 3 5 4 2]

Perfect! Notice how we go deep first (0 → 1 → 3 → 5) before backtracking to explore the other branch (4 → 2).

Testing Our Implementation

Let’s write a simple test to verify our implementation works correctly:

func TestDFSVisitsAllVertices(t *testing.T) {
	g := NewGraph(5)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)

	result := g.DFS(0)

	if len(result) != 5 {
		t.Errorf("Expected 5 vertices, got %d", len(result))
	}

	// Verify all vertices were visited
	visited := make(map[int]bool)
	for _, v := range result {
		visited[v] = true
	}

	for i := 0; i < 5; i++ {
		if !visited[i] {
			t.Errorf("Vertex %d was not visited", i)
		}
	}
}

Iterative DFS (Bonus)

If you want to avoid recursion (useful for very large graphs), here’s an iterative version using an explicit stack:

// DFSIterative performs DFS iteratively using an explicit stack
func (g *Graph) DFSIterative(start int) []int {
	visited := make(map[int]bool)
	var result []int
	var stack []int

	stack = append(stack, start)
	visited[start] = true

	for len(stack) > 0 {
		// Pop from stack
		vertex := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		result = append(result, vertex)
		fmt.Printf("Visiting vertex %d\n", vertex)

		// Push all unvisited neighbors onto the stack
		for _, neighbor := range g.edges[vertex] {
			if !visited[neighbor] {
				visited[neighbor] = true
				stack = append(stack, neighbor)
			}
		}
	}

	return result
}

Conclusion

Awesome! We now have a working implementation of the Depth-First Search algorithm in Go. We’ve built a Graph struct, implemented both recursive and iterative versions of DFS, and tested our implementation. DFS is a fundamental algorithm that you’ll use in many different scenarios, from pathfinding to topological sorting.

Quiz Time

Try your hand at these questions below to validate what we’ve just covered in this lesson: