Navigating the Network

[!NOTE] This module explores the core principles of Graph Traversals (BFS & DFS), deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Graphs are nodes (vertices) connected by edges. Unlike trees, graphs can have cycles. To traverse them, we need to track visited nodes to avoid infinite loops.

Breadth-First Search (BFS)

• Strategy: Explore layer by layer (ripples in a pond).
• Data Structure: Queue (FIFO).
• Use Case: Shortest Path in unweighted graphs.

Depth-First Search (DFS)

• Strategy: Explore as deep as possible, then backtrack (maze solving).
• Data Structure: Stack (LIFO) or Recursion.
• Use Case: Connectivity, Cycle Detection, Topological Sort.

---

2. Interactive Analysis

Select a start node and watch the traversal order.

BFS (Queue) DFS (Recursion)

Ready.

---

3. Implementation

Java

Go

// BFS using Queue
public void bfs(int start, List<List<Integer>> adj) {
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> q = new LinkedList<>();

    visited[start] = true;
    q.offer(start);

    while (!q.isEmpty()) {
        int u = q.poll();
        System.out.print(u + " ");

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                q.offer(v);
            }
        }
    }
}

// DFS using Recursion
public void dfs(int u, List<List<Integer>> adj, boolean[] visited) {
    visited[u] = true;
    System.out.print(u + " ");

    for (int v : adj.get(u)) {
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

// BFS
func BFS(start int, adj [][]int) {
    visited := make(map[int]bool)
    q := []int{start}
    visited[start] = true

    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        fmt.Print(u, " ")

        for _, v := range adj[u] {
            if !visited[v] {
                visited[v] = true
                q = append(q, v)
            }
        }
    }
}

// DFS
func DFS(u int, adj [][]int, visited map[int]bool) {
    visited[u] = true
    fmt.Print(u, " ")

    for _, v := range adj[u] {
        if !visited[v] {
            DFS(v, adj, visited)
        }
    }
}

---

4. Complexity Analysis

Strategy	Time	Space	Notes
BFS	O(V + E)	O(V)	Queue stores at most one layer of vertices.
DFS	O(V + E)	O(V)	Recursion stack depth can be V (line graph).

V is Vertices (Nodes), E is Edges.