# How BFS and DFS Graph Traversal Algorithms Are Implemented in Hello-Algo

> Explore BFS and DFS graph traversal algorithms in Hello-Algo Go implementations. Learn how adjacency lists, visited sets, queues, and recursion power these essential graph search techniques.

- Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo)
- Tags: deep-dive
- Published: 2026-02-25

---

**BFS and DFS graph traversal algorithms in the hello-algo repository are implemented using an adjacency-list representation with a visited set, where BFS uses a slice-based queue for level-order traversal in [`graph_bfs.go`](https://github.com/krahets/hello-algo/blob/main/graph_bfs.go) and DFS uses a recursive helper function for depth-first exploration in [`graph_dfs.go`](https://github.com/krahets/hello-algo/blob/main/graph_dfs.go).**

The `krahets/hello-algo` educational repository provides clean, reference implementations of fundamental graph algorithms in Go. The graph chapter models an undirected graph using an adjacency list structure, with both traversal methods operating directly on this representation while utilizing a **visited set** to prevent cycles and redundant processing.

## Core Data Structures for Graph Traversal

### Vertex and Adjacency List Representation

The implementation relies on two primary structures defined in separate files:

- **`Vertex`** ([[`codes/go/pkg/vertex.go`](https://github.com/krahets/hello-algo/blob/main/codes/go/pkg/vertex.go)](https://github.com/krahets/hello-algo/blob/main/codes/go/pkg/vertex.go)): A simple struct representing a graph node with a single integer field `Val`.
- **`graphAdjList`** ([[`codes/go/chapter_graph/graph_adjacency_list.go`](https://github.com/krahets/hello-algo/blob/main/codes/go/chapter_graph/graph_adjacency_list.go)](https://github.com/krahets/hello-algo/blob/main/codes/go/chapter_graph/graph_adjacency_list.go)): Stores the graph as a map `map[Vertex][]Vertex` where each key maps to its adjacent vertices. This file also provides helper methods like `addEdge`, `addVertex`, and `print`.

All traversal algorithms accept a `graphAdjList` pointer and a starting `Vertex`, operating on the adjacency map directly.

## Breadth-First Search (BFS) Implementation

The BFS graph traversal algorithm is implemented in [[`codes/go/chapter_graph/graph_bfs.go`](https://github.com/krahets/hello-algo/blob/main/codes/go/chapter_graph/graph_bfs.go)](https://github.com/krahets/hello-algo/blob/main/codes/go/chapter_graph/graph_bfs.go) using an iterative approach with a FIFO queue.

### Algorithm Steps

1. **Initialization**: Create a result slice `res`, a `visited` map for O(1) containment checks, and initialize a queue slice with the start vertex.
2. **Processing Loop**: While the queue contains elements:
   - Dequeue the front vertex (`vet := queue[0]`).
   - Append it to `res`.
   - Iterate through all adjacent vertices (`g.adjList[vet]`).
   - For each unvisited neighbor, mark it visited and enqueue it.
3. **Return**: The ordered slice representing level-order traversal.

### BFS Code Implementation

```go
func graphBFS(g *graphAdjList, startVet Vertex) []Vertex {
    res := make([]Vertex, 0)
    visited := map[Vertex]struct{}{startVet: {}}
    queue := []Vertex{startVet}
    for len(queue) > 0 {
        vet := queue[0]
        queue = queue[1:]
        res = append(res, vet)
        for _, adjVet := range g.adjList[vet] {
            if _, ok := visited[adjVet]; !ok {
                queue = append(queue, adjVet)
                visited[adjVet] = struct{}{}
            }
        }
    }
    return res
}

```

**Key Implementation Details**:
- The queue is implemented as a plain slice for clarity in educational contexts.
- The `visited` map uses empty struct values to minimize memory overhead while providing fast lookups.

## Depth-First Search (DFS) Implementation

The DFS graph traversal algorithm is implemented in [[`codes/go/chapter_graph/graph_dfs.go`](https://github.com/krahets/hello-algo/blob/main/codes/go/chapter_graph/graph_dfs.go)](https://github.com/krahets/hello-algo/blob/main/codes/go/chapter_graph/graph_dfs.go) using a recursive approach that leverages the call stack.

### Algorithm Structure

The implementation uses two functions:
- **`dfs`**: A private helper function that performs the recursive traversal.
- **`graphDFS`**: The public entry point that initializes state and invokes the helper.

### DFS Code Implementation

```go
func dfs(g *graphAdjList, visited map[Vertex]struct{}, res *[]Vertex, vet Vertex) {
    *res = append(*res, vet)
    visited[vet] = struct{}{}
    for _, adjVet := range g.adjList[vet] {
        if _, ok := visited[adjVet]; !ok {
            dfs(g, visited, res, adjVet)
        }
    }
}

/* Deep-first traversal entry point */
func graphDFS(g *graphAdjList, startVet Vertex) []Vertex {
    res := make([]Vertex, 0)
    visited := make(map[Vertex]struct{})
    dfs(g, visited, &res, startVet)
    return res
}

```

**Key Implementation Details**:
- The result slice is passed as a pointer (`*[]Vertex`) so all recursive calls append to the same underlying array.
- Recursion naturally provides the stack behavior required for depth-first exploration.
- The `visited` map prevents infinite loops in cyclic graphs.

## Practical Usage Example

The following complete example demonstrates how to construct a graph and run both BFS and DFS graph traversal algorithms:

```go
package main

import (
    "fmt"

    . "github.com/krahets/hello-algo/pkg"
    "github.com/krahets/hello-algo/codes/go/chapter_graph"
)

func main() {
    // Build vertices 0-5
    vets := ValsToVets([]int{0, 1, 2, 3, 4, 5})

    // Define undirected edges
    edges := [][]Vertex{
        {vets[0], vets[1]}, {vets[0], vets[2]},
        {vets[1], vets[3]}, {vets[2], vets[3]},
        {vets[3], vets[4]}, {vets[4], vets[5]},
    }

    // Construct the adjacency-list graph
    g := chapter_graph.NewGraphAdjList(edges)

    // BFS from vertex 0
    bfsOrder := chapter_graph.GraphBFS(g, vets[0])
    fmt.Println("BFS order:", VetsToVals(bfsOrder))

    // DFS from vertex 0
    dfsOrder := chapter_graph.GraphDFS(g, vets[0])
    fmt.Println("DFS order:", VetsToVals(dfsOrder))
}

```

**Example Output**:

```

BFS order: [0 1 2 3 4 5]
DFS order: [0 1 3 2 4 5]

```

This example illustrates the level-order nature of BFS versus the deep-path exploration of DFS on the same undirected graph structure.

## Summary

- **BFS and DFS graph traversal algorithms** in `krahets/hello-algo` operate on an adjacency-list representation defined in [`graph_adjacency_list.go`](https://github.com/krahets/hello-algo/blob/main/graph_adjacency_list.go).
- **BFS** uses an iterative approach with a slice-based queue and a `visited` map to process vertices in level-order, implemented in [`graph_bfs.go`](https://github.com/krahets/hello-algo/blob/main/graph_bfs.go).
- **DFS** uses a recursive helper function that leverages the call stack for deep exploration, passing the result slice by reference to accumulate the traversal order, implemented in [`graph_dfs.go`](https://github.com/krahets/hello-algo/blob/main/graph_dfs.go).
- Both algorithms rely on the simple `Vertex` struct from [`vertex.go`](https://github.com/krahets/hello-algo/blob/main/vertex.go) and prevent cycles using a `map[Vertex]struct{}` visited set.

## Frequently Asked Questions

### What data structure does hello-algo use to represent graphs for BFS and DFS?

The repository uses an **adjacency list** implemented as a Go map (`map[Vertex][]Vertex`) in [`graph_adjacency_list.go`](https://github.com/krahets/hello-algo/blob/main/graph_adjacency_list.go). This structure maps each vertex to a slice of its neighboring vertices, providing efficient O(1) access to adjacency information and O(V + E) space complexity.

### Why does the BFS implementation use a slice instead of a proper queue data structure?

The BFS code in [`graph_bfs.go`](https://github.com/krahets/hello-algo/blob/main/graph_bfs.go) uses a plain Go slice (`[]Vertex`) as a FIFO queue for educational clarity. While this requires O(n) time for the dequeue operation (`queue = queue[1:]`) due to slice reallocation, it is sufficient for the small-scale examples in the learning context and avoids importing container libraries that might distract from the core algorithm logic.

### How does the DFS implementation avoid infinite loops in cyclic graphs?

The DFS implementation prevents infinite recursion by maintaining a **`visited` map** (`map[Vertex]struct{}`) that tracks which vertices have already been processed. Before recursing into a neighbor in the `dfs` helper function, the code checks `if _, ok := visited[adjVet]; !ok`, ensuring each vertex is visited only once regardless of graph cycles.

### Can these traversal functions handle disconnected graphs?

The current implementations in [`graph_bfs.go`](https://github.com/krahets/hello-algo/blob/main/graph_bfs.go) and [`graph_dfs.go`](https://github.com/krahets/hello-algo/blob/main/graph_dfs.go) are designed to traverse only the **connected component** reachable from the specified start vertex. To traverse a disconnected graph completely, you would need to wrap these functions in an outer loop that iterates over all vertices, checking the `visited` set to ensure each component's traversal is initiated from an unvisited starting point.