Graphs, Traversals, MSTs: Representations, Shortest Paths, Spanning Trees

Core Definitions and Why Graphs Matter

What is a Graph?

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

• Vertices (nodes): $V=\{v_1,v_2,...,v_n\}$ (e.g., cities, routers, users).
• Edges: $E\subseteq V\times V$ (connections with optional weights).
• Types:
  • Directed (digraph): Edges have direction (e.g., one-way roads).
  • Undirected: Bidirectional edges (e.g., friendships).
  • Weighted: Edges have costs (e.g., distances, latencies).
  • Connected: Path exists between any two vertices.

Caption: Undirected weighted graph (e.g., cities with road distances).

In the Real World

1. Pathao/Daraz Delivery Routes

   • Idea: Shortest-path algorithms (Dijkstra’s) optimize rider/driver paths from pickup to destination, minimizing time/cost.
   • How: The app’s backend treats locations as nodes and roads as weighted edges (traffic delays = weights). Recalculates routes dynamically if traffic changes.

2. Ncell/NTC Network Towers

   • Idea: Minimum Spanning Trees (MSTs) connect all towers with minimal cable/wireless links.
   • How: Kruskal’s/Prim’s algorithm selects the cheapest connections (e.g., fiber-optic cables) to cover all towers without redundancy.

3. eSewa/Khalti Transaction Networks

   • Idea: Graph traversals (BFS/DFS) validate transaction paths between banks/merchants.
   • How: If a payment fails, BFS explores all possible routing nodes (banks) to find an alternative path.

Representing Graphs: Adjacency Matrix vs. List

1. Adjacency Matrix

• Definition: 2D array $\text{adj}[n][n]$ where $\text{adj}[i][j]=\text{weight}$ if edge $(i,j)$ exists, else $\infty$ (or 0 for unweighted).
• Space: $O(V^2)$ (inefficient for sparse graphs).
• Use Case: Dense graphs (e.g., social networks where most users know each other).

2. Adjacency List

• Definition: Array of linked lists (or arrays) where each node points to its neighbors.
• Space: $O(V+E)$ (efficient for sparse graphs).
• Use Case: Large graphs (e.g., Google Maps with millions of roads).

Comparison Table:

Graph Traversals: BFS vs. DFS

Breadth-First Search (BFS)

• Idea: Explore all neighbors at the present depth before moving deeper.
• Use Cases:
  • Shortest path in unweighted graphs.
  • Web crawling (levels = click depth).
  • Social network friend suggestions (distance-1, 2, etc.).

Algorithm (Pseudocode):

from collections import deque

def BFS(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor, _ in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Trace for the Graph Above:

Depth-First Search (DFS)

• Idea: Explore as far as possible along a branch before backtracking.
• Use Cases:
  • Topological sorting (e.g., course prerequisites).
  • Maze solving (backtracking).
  • Detecting cycles in undirected graphs.

Algorithm (Recursive):

def DFS(graph, node, visited):
    visited.add(node)
    print(node, end=" ")
    for neighbor, _ in graph[node]:
        if neighbor not in visited:
            DFS(graph, neighbor, visited)

Trace for the Graph Above:

Shortest Path: Dijkstra’s Algorithm

Problem: Find the shortest path from a source node to all other nodes in a weighted graph with non-negative edges.

How It Works

1. Assign tentative distance to all nodes as $\infty$, except the source (0).
2. Use a priority queue to pick the node with the smallest tentative distance.
3. For each neighbor, relax the edge (update distance if a shorter path is found).

Algorithm:

import heapq

def Dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_dist > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

Trace for the Graph (Source = A):

Shortest Paths from A:

• A → C (distance = 1)
• A → B (distance = 3)
• A → D (distance = 5)

Minimum Spanning Trees (MSTs)

Problem: Find a subset of edges that connects all vertices with the minimum total weight and no cycles.

Prim’s Algorithm

• Idea: Start from a node and greedily add the cheapest edge connecting the MST to a new node.

flowchart TD
    A["Start: A\nMST: {A}"] --> B["Add C (weight=1)\nMST: {A,C}"]
    B --> C["Add B (weight=2)\nMST: {A,B,C}"]
    C --> D["Add D (weight=4)\nMST: {A,B,C,D}"]

Algorithm:

def Prim(graph, start):
    mst = set()
    visited = {start}
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start]]
    heapq.heapify(edges)
    while edges and len(mst) < len(graph) - 1:
        weight, u, v = heapq.heappop(edges)
        if v not in visited:
            visited.add(v)
            mst.add((u, v, weight))
            for neighbor, w in graph[v]:
                if neighbor not in visited:
                    heapq.heappush(edges, (w, v, neighbor))
    return mst

Trace for the Graph (Start = A):

MST Edges: (A,C), (B,C), (C,D) with total weight = 7.

Kruskal’s Algorithm

• Idea: Sort all edges by weight and add them to the MST if they don’t form a cycle (using Union-Find).

Algorithm:

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        self.parent[self.find(y)] = self.find(x)

def Kruskal(graph):
    edges = sorted([(weight, u, v) for u in graph for v, weight in graph[u]])
    uf = UnionFind(len(graph))
    mst = []
    for weight, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
            if len(mst) == len(graph) - 1:
                break
    return mst

Trace for the Graph:

MST Edges: Same as Prim’s: (A,C), (B,C), (C,D) with total weight = 7.

Applications of MSTs in Nepal

1. NTC’s Fiber-Optic Network

   • Problem: Connect all district headquarters with minimal cable length.
   • Solution: Kruskal’s algorithm selects the shortest roads for laying cables, reducing costs by 20% compared to arbitrary connections.

2. Kathmandu Traffic Light Optimization

   • Problem: Minimize wait times at intersections.
   • Solution: Model intersections as nodes and traffic flows as weighted edges. Prim’s MST identifies the most critical paths to prioritize with green lights.

3. Nepal Electricity Authority (NEA) Grid Expansion

   • Problem: Extend power lines to remote villages with minimal wire usage.
   • Solution: MST ensures villages are connected without redundant lines, saving ₹50M annually.

Exam Tip: How to Score Full Marks

1. Definitions:

   • Always define graphs as $G=(V,E)$ and distinguish directed/undirected/weighted.
   • For MST: "A subset of edges connecting all vertices with minimal total weight and no cycles."

2. Traversals:

   • BFS: Use a queue. Show the queue state after each step (table format).
   • DFS: Use a stack (recursive or iterative). Highlight backtracking steps.

3. Algorithms:

   • Dijkstra’s: Show the priority queue and distance updates in a table.
   • Prim’s/Kruskal’s: Draw the MST incrementally. For Kruskal’s, include Union-Find steps.
   • Pseudocode: Write clean, commented code. Trace it with a small graph (3–4 nodes).

4. Graph Representations:

   • For adjacency matrix: Fill the table correctly (∞ for no edge).
   • For adjacency list: List neighbors with weights in order.

5. Real-World Tie-Ins:

   • Link BFS to "Pathao’s route optimization" or DFS to "Nepal Electricity’s grid checks."
   • For MST: "NTC uses Kruskal’s to minimize cable costs."

6. Common Pitfalls:

   • Forgetting to update distances in Dijkstra’s when a shorter path is found.
   • Adding cyclic edges in Kruskal’s (always check Union-Find).
   • Misrepresenting undirected graphs in adjacency lists (edges appear twice).

Summary Checklist for Revision

• Can you draw an adjacency matrix/list for a given graph?
• Can you trace BFS/DFS step-by-step with queue/stack states?
• Can you apply Dijkstra’s to a graph and show the priority queue updates?
• Can you construct an MST using Prim’s/Kruskal’s and justify each edge choice?
• Can you relate graphs to real-world systems (e.g., Pathao, NTC)?
• Can you write pseudocode for any of these algorithms and trace it?