Implementing Breadth-First Search in Go

👋 Welcome Gophers! In this lesson, we are going to be implementing the Breadth-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 07-bfs/. We’ll reuse the same Graph struct from our DFS implementation but implement BFS instead.

First, let’s define our Graph struct:

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 BFS function using a queue (slice):

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

	// Start by adding the start vertex to the queue
	queue = append(queue, start)
	visited[start] = true

	// Continue while the queue is not empty
	for len(queue) > 0 {
		// Dequeue the first vertex
		vertex := queue[0]
		queue = queue[1:]

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

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

	return result
}

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

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

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

	// Add the same edges as our DFS example for comparison
	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("\nBFS traversal starting from vertex 0:")
	result := g.BFS(0)
	fmt.Printf("Traversal order: %v\n", result)
}

Let’s run this and compare it with DFS:

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

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

Notice the difference from DFS! BFS explores all neighbors of the current level (0 → 1, 2 → 3, 4 → 5) before going deeper, while DFS went as deep as possible first.

Finding Shortest Path

One of the most useful applications of BFS is finding the shortest path between two nodes. Let’s add that functionality:

// ShortestPath finds the shortest path between start and end vertices
func (g *Graph) ShortestPath(start, end int) []int {
	visited := make(map[int]bool)
	parent := make(map[int]int)
	var queue []int

	queue = append(queue, start)
	visited[start] = true
	parent[start] = -1

	for len(queue) > 0 {
		vertex := queue[0]
		queue = queue[1:]

		if vertex == end {
			break
		}

		for _, neighbor := range g.edges[vertex] {
			if !visited[neighbor] {
				visited[neighbor] = true
				parent[neighbor] = vertex
				queue = append(queue, neighbor)
			}
		}
	}

	// Reconstruct the path
	var path []int
	current := end
	for current != -1 {
		path = append([]int{current}, path...)
		current = parent[current]
	}

	return path
}

Test the shortest path function:

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

	g := NewGraph(6)
	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("\nBFS traversal starting from vertex 0:")
	result := g.BFS(0)
	fmt.Printf("Traversal order: %v\n", result)

	fmt.Println("\nShortest path from 0 to 5:")
	path := g.ShortestPath(0, 5)
	fmt.Printf("Path: %v\n", path)
}

Running this will show:

Shortest path from 0 to 5:
Path: [0 2 4 5]

Testing Our Implementation

Let’s write tests to verify our BFS implementation:

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

	result := g.BFS(0)

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

	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)
		}
	}
}

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

	result := g.BFS(0)

	// In BFS, nodes at the same level should be visited consecutively
	// 0 is at level 0
	// 1, 2 are at level 1
	// 3, 4 are at level 2
	if result[0] != 0 {
		t.Errorf("First visited should be 0")
	}
}

Conclusion

Awesome! We now have a working implementation of the Breadth-First Search algorithm in Go. BFS is especially useful for finding shortest paths in unweighted graphs and exploring nodes level by level. The key difference from DFS is the use of a queue instead of a stack, which fundamentally changes how the algorithm explores the graph.

Quiz Time

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