Graphs & Traversal: Representations, BFS/DFS, Shortest Paths, Spanning Trees

TAKEAWAYS:

• Graphs model relationships between discrete objects (nodes/vertices) with weighted/unweighted edges, used in maps, networks, and dependency systems.
• Adjacency matrix and lists are two primary representations, each with trade-offs for storage and traversal efficiency.
• BFS (breadth-first search) explores nodes level-by-level, ideal for shortest paths in unweighted graphs, while DFS (depth-first search) uses recursion or stacks for pathfinding and cycle detection.
• Dijkstra’s algorithm finds shortest paths in weighted graphs with non-negative edges, critical for GPS navigation and package delivery routing.
• Minimum Spanning Trees (Prim’s/Kruskal’s) optimize network connectivity (e.g., NTC’s fiber backbone) by minimizing total edge weight.
• Graph traversal algorithms underpin real-world systems like Pathao’s ride-matching, Daraz’s order routing, and NEPSE’s stock market connectivity.

1. Introduction to Graphs

A graph $G=(V,E)$ consists of:

• Vertices (nodes) $V$: discrete entities (e.g., cities, users, servers).
• Edges: connections between vertices, optionally weighted (e.g., road lengths, call costs).

Types of Graphs

graph TD
  A["Graph Types"] --> B[Undirected
  (A↔B)]
  A --> C[Directed
  (A→B)]
  A --> D[Weighted
  (Edges have values)]
  A --> E[Unweighted
  (Binary edges)]
  A --> F[Cyclic
  (Contains loops)]
  A --> G[Acyclic
  (No loops, e.g., trees)]

Real-world example:

• Pathao’s ride-matching: Directed graph where edges represent driver availability (one-way) and weights are time/distance to pick up passengers.
• NEPSE stock market: Undirected weighted graph where vertices are stocks and edges represent transaction costs between them.

2. Graph Representations

Adjacency Matrix

A 2D array $\text{adj}[V][V]$ where:

• $\text{adj}[i][j]=1$ if edge $(i,j)$ exists.
• For weighted graphs, store edge weights.

Pros: Fast edge lookup ($O(1)$), easy to check if two vertices are connected. Cons: Wastes space for sparse graphs (e.g., social networks with few connections).

Adjacency List

A list of lists where each vertex $v$ has a list of adjacent vertices (and weights if applicable).

A → [B(3), D(5)] B → [A(3), C(2)] C → [B(2), D(1)] D → [A(5), C(1)]

Pros: Space-efficient for sparse graphs ($O(V+E)$). Cons: Edge lookup is $O(V)$.

Comparison Table

3. Graph Traversal Algorithms

Breadth-First Search (BFS)

Explores nodes level-by-level using a queue. Used for:

• Shortest path in unweighted graphs.
• Web crawling (e.g., Google’s initial page indexing).
• Social network analysis (e.g., finding friends-of-friends).

Algorithm (Pseudocode)

function BFS(graph, start):
    queue = Queue()
    queue.enqueue(start)
    visited = {start}

    while not queue.isEmpty():
        vertex = queue.dequeue()
        print(vertex)  # Process vertex
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)

Traced Example: Find shortest path from A to D in the adjacency list above.

Step 1: Queue = [A], Visited = {A}
Step 2: Dequeue A → Enqueue B, D. Queue = [B, D], Visited = {A, B, D}
Step 3: Dequeue B → Enqueue C. Queue = [D, C], Visited = {A, B, D, C}
Step 4: Dequeue D → Terminate (D is target).
Path: A → D (length 1 edge).

Visualization of BFS Levels

Level 0: A
Level 1: B, D
Level 2: C

Depth-First Search (DFS)

Explores as far as possible along a branch before backtracking, using a stack (or recursion). Used for:

• Cycle detection (e.g., in compiler design).
• Topological sorting (e.g., course prerequisites).
• Maze solving (e.g., Pathao’s route optimization).

Algorithm (Recursive)

function DFS(graph, vertex, visited):
    if vertex not in visited:
        visited.add(vertex)
        print(vertex)
        for neighbor in graph[vertex]:
            DFS(graph, neighbor, visited)

Traced Example: DFS on the same graph starting at A.

Step 1: Visit A → Recurse to B → Recurse to C (no neighbors) → Backtrack to B → Backtrack to A → Recurse to D → Terminate.
Order: A, B, C, D

Comparison: BFS vs. DFS

4. Shortest Path Algorithms

Dijkstra’s Algorithm

Finds the shortest path from a source vertex to all others in a weighted graph with non-negative edges. Steps:

1. Initialize distances: $\text{dist}[source]=0$, others $\infty$.
2. Use a priority queue to always expand the closest unvisited vertex.
3. Relax edges: update distances if a shorter path is found.

Pseudocode

function Dijkstra(graph, start):
    dist = {v: ∞ for v in graph}
    dist[start] = 0
    priority_queue = PriorityQueue()
    priority_queue.put(start, 0)

    while not priority_queue.isEmpty():
        current = priority_queue.get()
        for neighbor, weight in graph[current]:
            new_dist = dist[current] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                priority_queue.put(neighbor, new_dist)
    return dist

Worked Example: Find shortest path from A to Z in the following graph (assume weights are edge lengths).

Step-by-Step Execution

Shortest Path: A → B → C → D → E → F → G → H → I → J → K → L → M → N → O → P → Q → R → S → T → U → V → W → X → Y → Z (Total: 18 units).

Real-world tie-in:

• NTC’s fiber network: Dijkstra’s algorithm optimizes data routes between exchange centers to minimize latency.
• Daraz’s order delivery: Finds the fastest path from warehouse to customer, accounting for traffic (weights) and road closures.

5. Minimum Spanning Trees (MST)

A subset of edges that connects all vertices with the minimum total weight, used for:

• Network design (e.g., NTC’s backbone).
• Cluster analysis (e.g., grouping similar users in Khalti’s payment network).

Prim’s Algorithm

1. Start with an arbitrary vertex.
2. Greedily add the cheapest edge connecting the current tree to a new vertex.
3. Repeat until all vertices are included.

Pseudocode

function Prim(graph, start):
    mst = {start}
    edges = PriorityQueue()
    for neighbor, weight in graph[start]:
        edges.put(weight, (start, neighbor))

    while len(mst) < V:
        weight, (u, v) = edges.get()
        if v not in mst:
            mst.add(v)
            for neighbor, w in graph[v]:
                if neighbor not in mst:
                    edges.put(w, (v, neighbor))
    return mst

Example: Find MST for the graph below (weights = edge costs).

Steps:

1. Start at A → Add edge A-B (weight 1).
2. Add edge B-C (weight 2).
3. Add edge C-D (weight 3). MST Edges: A-B, B-C, C-D (Total weight: 6).

Comparison: Prim’s vs. Kruskal’s

6. Applications in Nepal

Pathao’s Ride-Matching

• Graph Model: Vertices = drivers/users, edges = possible routes (weighted by time/distance).
• Algorithm: Dijkstra’s to find the fastest driver to a pickup location.
• Real Impact: Reduces passenger wait times by 30% in Kathmandu’s congested areas.

NEPSE Stock Market

• Graph Model: Vertices = stocks, edges = transaction costs between brokers.
• Algorithm: Prim’s to design the cheapest network of brokers ensuring all stocks are connected.
• Real Impact: Lowers trading fees by optimizing broker connections.

NTC’s Fiber Network

• Graph Model: Vertices = exchange centers, edges = fiber cables (weighted by cost/latency).
• Algorithm: Kruskal’s to build the lowest-cost network covering all cities.
• Real Impact: Reduced internet latency in rural Nepal by 40%.

Exam Tip

1. Graph Representations:

   • Always compare adjacency matrix vs. list for a given scenario (e.g., "Why does NTC use adjacency lists?").
   • Draw both representations for a small graph (3–4 vertices) in exams.

2. BFS/DFS:

   • For BFS, show levels explicitly (like the figure above). For DFS, show the recursion stack.
   • If asked to find a path, label the traversal order with arrows (e.g., A → B → C).

3. Dijkstra’s Algorithm:

   • Memorize the priority queue step. Always update distances when a shorter path is found.
   • For the exam, assume the graph is connected and weights are non-negative.

4. MST:

   • Prim’s is vertex-based; Kruskal’s is edge-based. Know when to use each.
   • Draw the MST edges in bold on the original graph.

5. Real-world Tie-ins:

   • Link every algorithm to a Nepalese example (e.g., "Pathao uses BFS to find the closest driver").
   • If the exam includes a graph, assume it’s a real-world scenario (e.g., "This is NTC’s network").

6. Time Complexity:

   • BFS/DFS: $O(V+E)$.
   • Dijkstra’s: $O((V+E)\log V)$ with a priority queue.
   • Prim’s: $O(E\log V)$.

Common Pitfalls:

• Forgetting to mark visited nodes in BFS/DFS (leads to infinite loops).
• Not relaxing edges in Dijkstra’s (missing shorter paths).
• Mixing up Prim’s (vertex) and Kruskal’s (edge) algorithms.

Final Visual Summary