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

Question

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.

Accepted Answer

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 and DFS uses a recursive helper function for depth-first exploration in 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)): 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)): 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) using an iterative approach with a FIFO queue.

Algorithm Steps

Initialization: Create a result slice res, a visited map for O(1) containment checks, and initialize a queue slice with the start vertex.
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.
Return: The ordered slice representing level-order traversal.

BFS Code Implementation

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

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:

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.
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.
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.
Both algorithms rely on the simple Vertex struct from 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. 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 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 and 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.