15. BFS & DFS (Graph/Tree Traversal)

🧸 ELI5 (BFS - Breadth First Search): You're spreading a rumor at school. First you tell your close friends (1 step away). Then they tell their friends (2 steps away). You spread outward in rings, layer by layer — like ripples in a pond.

🧸 ELI5 (DFS - Depth First Search): You're exploring a maze. You pick a path and go as deep as possible until you hit a dead end, then backtrack to the last fork and try a different path. You commit fully to one direction before trying another.

🌍 Real life: BFS = "how many people are within 2 friendship-steps of me?" (LinkedIn's "2nd degree connections"), finding the shortest path in an unweighted maze. DFS = solving a maze by hand, exploring a file system recursively, detecting cycles.

📝 Pseudocode (BFS):

function bfs(graph, start):
    visited = {start}
    queue = [start]
    while queue is not empty:
        current = dequeue(queue)
        print(current)
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                enqueue(queue, neighbor)

📝 Pseudocode (DFS):

function dfs(graph, current, visited={}):
    if current in visited: return
    visited.add(current)
    print(current)
    for neighbor in graph[current]:
        dfs(graph, neighbor, visited)

🐹 Go (BFS):

package main

import "fmt"

func bfs(graph map[string][]string, start string) {
	visited := map[string]bool{start: true}
	queue := []string{start}

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]
		fmt.Println("visiting:", current)

		for _, neighbor := range graph[current] {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}
}

func main() {
	friendGraph := map[string][]string{
		"Alice": {"Bob", "Carol"},
		"Bob":   {"Alice", "Dave"},
		"Carol": {"Alice"},
		"Dave":  {"Bob"},
	}
	bfs(friendGraph, "Alice") // Alice, Bob, Carol, Dave (ring by ring)
}

🐹 Go (DFS):

package main

import "fmt"

func dfs(graph map[string][]string, current string, visited map[string]bool) {
	if visited[current] {
		return
	}
	visited[current] = true
	fmt.Println("visiting:", current)

	for _, neighbor := range graph[current] {
		dfs(graph, neighbor, visited)
	}
}

func main() {
	maze := map[string][]string{
		"Start": {"A", "B"},
		"A":     {"Start", "DeadEnd"},
		"B":     {"Start", "Exit"},
	}
	dfs(maze, "Start", map[string]bool{}) // dives deep down one path first
}

🇨 C (both BFS and DFS on the same integer-indexed adjacency-list Graph from #14 — BFS's queue is a plain array with head/tail indices, exactly Section 23.2's ring-buffer idea; DFS is recursion, exactly #9's "same problem, smaller size"):

#include <stdio.h>
#include <string.h>

#define MAX_NODES 16

typedef struct {
    char names[MAX_NODES][32];
    int  adj_list[MAX_NODES][MAX_NODES];
    int  adj_count[MAX_NODES];
    int  num_nodes;
} Graph;

int graph_add_node(Graph *g, const char *name) {
    strncpy(g->names[g->num_nodes], name, 31);
    return g->num_nodes++;
}

void graph_add_edge(Graph *g, int a, int b) {
    g->adj_list[a][g->adj_count[a]++] = b;
    g->adj_list[b][g->adj_count[b]++] = a;
}

void bfs(Graph *g, int start) {
    int visited[MAX_NODES] = {0};
    int queue[MAX_NODES], head = 0, tail = 0;

    visited[start] = 1;
    queue[tail++] = start;

    while (head < tail) {
        int current = queue[head++];
        printf("visiting: %s\n", g->names[current]);
        for (int i = 0; i < g->adj_count[current]; i++) {
            int neighbor = g->adj_list[current][i];
            if (!visited[neighbor]) { visited[neighbor] = 1; queue[tail++] = neighbor; }
        }
    }
}

void dfs(Graph *g, int current, int *visited) {
    if (visited[current]) return;
    visited[current] = 1;
    printf("visiting: %s\n", g->names[current]);
    for (int i = 0; i < g->adj_count[current]; i++) {
        dfs(g, g->adj_list[current][i], visited);
    }
}

int main(void) {
    Graph friendGraph = {0};
    int alice = graph_add_node(&friendGraph, "Alice");
    int bob   = graph_add_node(&friendGraph, "Bob");
    int carol = graph_add_node(&friendGraph, "Carol");
    int dave  = graph_add_node(&friendGraph, "Dave");
    graph_add_edge(&friendGraph, alice, bob);
    graph_add_edge(&friendGraph, alice, carol);
    graph_add_edge(&friendGraph, bob, dave);

    printf("-- BFS --\n");
    bfs(&friendGraph, alice); // Alice, Bob, Carol, Dave (ring by ring)

    printf("-- DFS --\n");
    int visited[MAX_NODES] = {0};
    dfs(&friendGraph, alice, visited); // dives deep down one path first
    return 0;
}

⏱️ Complexity: Both BFS and DFS = O(V + E) — you visit every person/place and every friendship/path once.