Graph Traversal: Exploring Your Network Systematically 🔍

Now that you know how to store graphs, let’s learn how to explore them! Graph traversal algorithms help you visit all the nodes in a graph in an organized way. We’ll learn two fundamental approaches: Breadth-First Search (BFS) and Depth-First Search (DFS).

Breadth-First Search: Meeting Friends Level by Level 👥

Imagine you’re at a party and you want to meet everyone. You start with your close friends, then their friends, then their friends’ friends. That’s breadth-first!

BFS explores the graph level by level, like ripples in a pond.

package main

import "fmt"

// Breadth-First Search implementation
type Graph struct {
    vertices int
    adjList  [][]int
}

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

func (g *Graph) AddEdge(from, to int) {
    g.adjList[from] = append(g.adjList[from], to)
    // For undirected graph
    g.adjList[to] = append(g.adjList[to], from)
}

func (g *Graph) BFS(startVertex int) []int {
    visited := make([]bool, g.vertices) // Track visited vertices
    queue := []int{startVertex}         // Queue for BFS
    visited[startVertex] = true
    result := []int{}                   // Order of visitation

    for len(queue) > 0 {
        // Dequeue vertex
        currentVertex := queue[0]
        queue = queue[1:]
        result = append(result, currentVertex)

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

    return result
}

func main() {
    g := NewGraph(6)

    // Create a friend network:
    // 0 -- 1 -- 2
    // |    |    |
    // 3 -- 4 -- 5
    g.AddEdge(0, 1)
    g.AddEdge(1, 2)
    g.AddEdge(2, 5)
    g.AddEdge(5, 4)
    g.AddEdge(4, 3)
    g.AddEdge(3, 0)
    g.AddEdge(1, 4)

    fmt.Println("BFS starting from vertex 0:")
    bfsOrder := g.BFS(0)
    fmt.Println(bfsOrder) // [0, 1, 3, 2, 4, 5]

    fmt.Println("BFS starting from vertex 2:")
    bfsOrder2 := g.BFS(2)
    fmt.Println(bfsOrder2) // [2, 1, 5, 0, 4, 3]
}

Step by step BFS from vertex 0:

1. Start at 0, mark visited, enqueue neighbors [1, 3]
2. Visit 1, enqueue its unvisited neighbors [2, 4]
3. Visit 3, enqueue its unvisited neighbors [4] (0 and 1 already visited)
4. Visit 2, enqueue its unvisited neighbors [5]
5. Visit 4, enqueue its unvisited neighbors [5] (already queued)
6. Visit 5, no unvisited neighbors

BFS Properties:

• Visits all nodes at distance k before distance k+1
• Uses a queue (FIFO: First In, First Out)
• Good for finding shortest paths in unweighted graphs

Depth-First Search: Following One Friend Deeply 🔍

Instead of meeting everyone level by level, you follow one friend as far as possible before backtracking. Like exploring a maze - go straight until you hit a dead end, then backtrack.

package main

import "fmt"

// Depth-First Search implementation
func (g *Graph) DFS(startVertex int) []int {
    visited := make([]bool, g.vertices)
    result := []int{}

    g.dfsHelper(startVertex, visited, &result)

    return result
}

func (g *Graph) dfsHelper(vertex int, visited []bool, result *[]int) {
    visited[vertex] = true
    *result = append(*result, vertex)

    // Visit all unvisited neighbors
    for _, neighbor := range g.adjList[vertex] {
        if !visited[neighbor] {
            g.dfsHelper(neighbor, visited, result)
        }
    }
}

// Iterative DFS (using stack)
func (g *Graph) DFSIterative(startVertex int) []int {
    visited := make([]bool, g.vertices)
    stack := []int{startVertex}
    result := []int{}

    for len(stack) > 0 {
        // Pop from stack
        currentVertex := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if !visited[currentVertex] {
            visited[currentVertex] = true
            result = append(result, currentVertex)

            // Push unvisited neighbors to stack
            for i := len(g.adjList[currentVertex]) - 1; i >= 0; i-- {
                neighbor := g.adjList[currentVertex][i]
                if !visited[neighbor] {
                    stack = append(stack, neighbor)
                }
            }
        }
    }

    return result
}

func main() {
    g := NewGraph(6)

    g.AddEdge(0, 1)
    g.AddEdge(1, 2)
    g.AddEdge(2, 5)
    g.AddEdge(5, 4)
    g.AddEdge(4, 3)
    g.AddEdge(3, 0)
    g.AddEdge(1, 4)

    fmt.Println("DFS (recursive) starting from vertex 0:")
    dfsOrder := g.DFS(0)
    fmt.Println(dfsOrder) // [0, 1, 2, 5, 4, 3]

    fmt.Println("DFS (iterative) starting from vertex 0:")
    dfsIterativeOrder := g.DFSIterative(0)
    fmt.Println(dfsIterativeOrder) // [0, 3, 4, 5, 2, 1]
}

Step by step DFS from vertex 0:

1. Start at 0, visit, go to first neighbor (1)
2. At 1, visit, go to first neighbor (2)
3. At 2, visit, go to first neighbor (5)
4. At 5, visit, go to first neighbor (4)
5. At 4, visit, go to first neighbor (3)
6. At 3, visit, go to first neighbor (0) - already visited, backtrack
7. Back at 4, no more neighbors, backtrack
8. Back at 5, no more neighbors, backtrack
9. Back at 2, no more neighbors, backtrack
10. Back at 1, no more neighbors, backtrack
11. Back at 0, no more neighbors, done

DFS Properties:

• Goes deep before wide
• Uses a stack (LIFO: Last In, First Out)
• Good for topological sorting and finding cycles

BFS vs DFS Comparison ⚖️

Finding Shortest Paths with BFS 🛣️

BFS can find the shortest path in an unweighted graph:

func (g *Graph) ShortestPath(start, end int) []int {
    visited := make([]bool, g.vertices)
    queue := []int{start}
    visited[start] = true

    // Track parent of each vertex to reconstruct path
    parent := make([]int, g.vertices)
    for i := range parent {
        parent[i] = -1
    }

    found := false
    for len(queue) > 0 && !found {
        current := queue[0]
        queue = queue[1:]

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

                if neighbor == end {
                    found = true
                    break
                }
            }
        }
    }

    // Reconstruct path
    if !found {
        return nil // No path found
    }

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

    return path
}

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

    path := g.ShortestPath(0, 5)
    fmt.Println("Shortest path from 0 to 5:", path) // [0, 1, 2, 5]
}

Detecting Cycles with DFS 🔄

DFS can detect if a graph has cycles:

func (g *Graph) HasCycle() bool {
    visited := make([]bool, g.vertices)
    recStack := make([]bool, g.vertices) // Track current recursion stack

    for vertex := 0; vertex < g.vertices; vertex++ {
        if !visited[vertex] {
            if g.hasCycleDFS(vertex, visited, recStack) {
                return true
            }
        }
    }

    return false
}

func (g *Graph) hasCycleDFS(vertex int, visited, recStack []bool) bool {
    visited[vertex] = true
    recStack[vertex] = true

    for _, neighbor := range g.adjList[vertex] {
        if !visited[neighbor] {
            if g.hasCycleDFS(neighbor, visited, recStack) {
                return true
            }
        } else if recStack[neighbor] {
            // Found back edge - cycle detected
            return true
        }
    }

    recStack[vertex] = false
    return false
}

func main() {
    // Create a cyclic graph
    cyclicGraph := NewGraph(4)
    cyclicGraph.AddEdge(0, 1)
    cyclicGraph.AddEdge(1, 2)
    cyclicGraph.AddEdge(2, 0) // Creates cycle: 0 -> 1 -> 2 -> 0
    cyclicGraph.AddEdge(1, 3)

    fmt.Println("Cyclic graph has cycle:", cyclicGraph.HasCycle()) // true

    // Create acyclic graph
    acyclicGraph := NewGraph(4)
    acyclicGraph.AddEdge(0, 1)
    acyclicGraph.AddEdge(1, 2)
    acyclicGraph.AddEdge(2, 3) // No cycles

    fmt.Println("Acyclic graph has cycle:", acyclicGraph.HasCycle()) // false
}

Practice Problems 🎯

1. Level Order: Use BFS to print nodes level by level
2. Path Exists: Check if a path exists between two nodes
3. Connected Components: Count separate friend groups in a social network
4. Maze Solver: Use BFS to find the shortest path out of a maze
5. Web Crawler: Simulate crawling web pages with DFS
6. Course Schedule: Use topological sort to check if courses can be completed

What’s Next? 🚀

Now that you can traverse graphs, the final lesson will cover advanced graph algorithms like shortest paths (Dijkstra’s), minimum spanning trees (Kruskal’s), and real-world applications!

Graph traversal is fundamental to almost all graph algorithms. Master BFS and DFS, and you’ll be able to solve complex network problems! 🌐