Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes in layers starting from a source node. It computes the shortest path distance (d-value) and predecessor (π-value) for each node in a directed graph.

The following Go code implements BFS using a adjacency list representation. The algorithm initializes all nodes with a distance of -1 (unvisited) and processes nodes level by level using a queue.

package main

import "fmt"

type Graph struct {
	adjList map[int][]int
}

func NewGraph() *Graph {
	return &Graph{adjList: make(map[int][]int)}
}

func (g *Graph) AddEdge(src, dest int) {
	g.adjList[src] = append(g.adjList[src], dest)
}

func (g *Graph) BFS(start int) (map[int]int, map[int]int) {
	dist := make(map[int]int)
	pred := make(map[int]int)
	visited := make(map[int]bool)

	for node := range g.adjList {
		dist[node] = -1
		pred[node] = -1
	}

	queue := []int{start}
	dist[start] = 0
	visited[start] = true

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

		for _, neighbor := range g.adjList[current] {
			if !visited[neighbor] {
				visited[neighbor] = true
				dist[neighbor] = dist[current] + 1
				pred[neighbor] = current
				queue = append(queue, neighbor)
			}
		}
	}
	return dist, pred
}

func main() {
	g := NewGraph()
	g.AddEdge(3, 2)
	g.AddEdge(3, 5)
	g.AddEdge(2, 1)
	g.AddEdge(2, 4)
	g.AddEdge(5, 4)

	d, π := g.BFS(3)
	fmt.Println("Distance values:", d)
	fmt.Println("Predecessor values:", π)
}

The output for this graph with source node 3 would be:

Distance values: map[1:2 2:1 3:0 4:2 5:1]
Predecessor values: map[1:2 2:3 3:-1 4:2 5:3]

This indicates node 3 has distance 0 (source), nodes 2 and 5 are at distance 1, while nodes 1 and 4 are at distance 2. The predecessor chain shows the shortest path relationships.