BFS e DFS visitam exatamente os mesmos nós (a parte do grafo alcançável a partir do início), só em ordem diferente. A escolha não é sobre velocidade, é sobre o que você quer. Quer o caminho mais curto em saltos? BFS. Quer descer uma cadeia de dependências até o fim? DFS. Os dois rodam em O(V+E) com lista de adjacência.
Lista de adjacência + BFS (fila)
type Graph map[int][]int
// BFS: fila FIFO; acha caminho mínimo em grafo não ponderado
func bfs(g Graph, start int) {
visited := map[int]bool{start: true}
dist := map[int]int{start: 0}
queue := []int{start}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:] // dequeue
for _, nb := range g[cur] {
if !visited[nb] {
visited[nb] = true
dist[nb] = dist[cur] + 1
queue = append(queue, nb)
}
}
}
}
DFS (recursão = call stack)
func dfs(g Graph, node int, visited map[int]bool) {
visited[node] = true
for _, nb := range g[node] {
if !visited[nb] {
dfs(g, nb, visited) // afunda
}
}
}