Graph Algorithms: Traversal, MST, Shortest Path & Applications

TAKEAWAYS:

• Graphs model real-world connections (roads, networks, dependencies) using vertices (nodes) and edges (connections) with weights for costs/distance.
• BFS explores level-by-level (shortest path in unweighted graphs), while DFS goes deep-first (useful for puzzles/maze-solving).
• Kruskal’s and Prim’s algorithms build minimum spanning trees (MST) by greedily selecting the cheapest edges—critical for network design (e.g., NTC’s fiber-optic backbone).
• Dijkstra’s finds the shortest path from a source to all nodes (used by Pathao for ride routing or Google Maps for navigation).
• Topological sorting orders tasks with dependencies (e.g., course prerequisites or project task scheduling).
• Time complexity varies: BFS/DFS = O(V+E), Kruskal’s = O(E log E), Dijkstra’s (with priority queue) = O((V+E) log V).

---

1. Graph Basics: Representations and Traversals

Graphs consist of vertices (nodes) and edges (connections). They can be:

• Directed (edges have direction, e.g., flight routes).
• Undirected (edges bidirectional, e.g., friendships).
• Weighted (edges have costs/distance, e.g., road networks).
• Unweighted (no costs, e.g., social networks).

Graph Representations

Two primary ways to store graphs in memory:

1. Adjacency Matrix (2D array):
   • matrix[i][j] = 1 if edge exists from vertex i to j.
   • Space: O(V²) (inefficient for sparse graphs).
   • Best for dense graphs (many edges).

2. Adjacency List (array of linked lists):
   • Each vertex stores a list of adjacent vertices.
   • Space: O(V + E) (efficient for sparse graphs).
   • Used in most real-world applications (e.g., Google Maps).

Graph Traversals

Two fundamental algorithms to explore graphs:

A. Breadth-First Search (BFS)

• Explores all neighbors at the present depth before moving deeper.
• Uses a queue (FIFO).
• Applications: Shortest path in unweighted graphs, web crawling, social network connections.

Algorithm Steps:

1. Start at the root node, mark it visited, enqueue it.
2. While queue is not empty:
   • Dequeue a node, process it.
   • Enqueue all its unvisited neighbors and mark them visited.

Worked Example: BFS on an Unweighted Graph Graph:

      A
    / | \
   B  C  D
  /    \
 E      F

BFS Traversal Order: A → B → C → D → E → F

Trace Table:

Real-World Use:

• Pathao Ride Routing: When you request a ride, Pathao’s algorithm uses BFS to find the nearest available driver (unweighted graph of drivers’ locations).
• WhatsApp Message Delivery: Messages spread level-by-level among contacts (BFS-like propagation).

B. Depth-First Search (DFS)

• Explores as far as possible along each branch before backtracking.
• Uses a stack (LIFO) or recursion.
• Applications: Solving puzzles (mazes), detecting cycles, topological sorting.

Algorithm Steps:

1. Start at the root node, mark it visited.
2. Recursively visit an unvisited neighbor.
3. Backtrack when no unvisited neighbors remain.

Worked Example: DFS on the Same Graph DFS Traversal Order: A → B → E → C → D → F

Trace Table:

Real-World Use:

• Nepal Electricity Authority (NEA) Power Grid: DFS helps detect loops or redundant connections in the electrical network to prevent blackouts.
• GitHub Dependency Resolution: When you install a Python package, pip uses DFS to resolve all nested dependencies recursively.

---

2. Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) is a subset of edges that:

• Connects all vertices.
• Has the minimum total weight.
• No cycles (a tree!).

Applications:

• Designing NTC’s fiber-optic network (connect cities with minimal cable cost).
• Khalti’s payment routing (minimize transaction fees between banks).
• Airport layover planning (connect cities with minimal flight costs).

Algorithms to Find MST

Two greedy algorithms:

A. Kruskal’s Algorithm

1. Sort all edges by weight in ascending order.
2. Add the smallest edge if it doesn’t form a cycle.
3. Repeat until V-1 edges are added.

Steps Visualized:

Worked Example: Graph:

      A
    / | \
   B(1)C(2)
    \   /
     \ /
      D(4,5)

Edges Sorted by Weight: A-B (1), A-C (2), B-D (4), C-D (5)

Trace Table:

Final MST Weight: 1 + 2 + 4 + 5 = 12

Real-World Tie-In:

• NTC’s Fiber-Optic Network: Suppose NTC needs to connect 4 cities (A: Kathmandu, B: Pokhara, C: Chitwan, D: Bharatpur) with fiber cables. The costs (in millions) are:
  • Kathmandu-Pokhara: 1
  • Kathmandu-Chitwan: 2
  • Pokhara-Chitwan: 3
  • Pokhara-Bharatpur: 4
  • Chitwan-Bharatpur: 5 Kruskal’s algorithm would select the edges Kathmandu-Pokhara (1), Kathmandu-Chitwan (2), Pokhara-Bharatpur (4), and Chitwan-Bharatpur (5) for a total cost of 12 million, the cheapest possible.

B. Prim’s Algorithm

1. Start with any vertex.
2. Add the cheapest edge from the current MST to a vertex not in the MST.
3. Repeat until all vertices are included.

Steps Visualized:

Worked Example: Graph: Same as above.

Trace Table:

Comparison of Kruskal’s and Prim’s:

Real-World Use:

• Daraz’s Warehouse Network: Daraz uses MST to connect its warehouses across Nepal with minimal shipping costs. If warehouses are in Kathmandu, Pokhara, and Biratnagar, the algorithm ensures the cheapest road/rail connections are used.

---

3. Shortest Path Algorithms

Find the path with the minimum total weight between two vertices.

A. Dijkstra’s Algorithm

• Finds the shortest path from a single source to all other vertices.
• Works only for graphs with non-negative weights.
• Uses a priority queue (min-heap).

Algorithm Steps:

1. Initialize distances: source = 0, others = ∞.
2. Extract the vertex u with the smallest distance.
3. For each neighbor v of u, relax the edge: dist[v] = min(dist[v], dist[u] + weight(u,v)).
4. Repeat until all vertices are processed.

Worked Example: Graph:

      A
    / | \
   B(1)C(4)
    \   /
     \ /
      D(2,3)

Source: A

Trace Table:

Shortest Paths:

• A → B: 1 (A-B)
• A → C: 4 (A-B-D-C)
• A → D: 3 (A-B-D)

Visualization of Relaxation:

Real-World Use:

• Pathao Ride Optimization: When you request a ride from Kathmandu to Lalitpur, Pathao’s algorithm uses Dijkstra’s to find the fastest route avoiding traffic (weighted by distance + estimated travel time).
• Google Maps Navigation: If you search for "Kathmandu to Pokhara," Google uses Dijkstra’s (or A*) to plot the shortest path, considering road weights (distance + tolls + traffic).

B. Bellman-Ford Algorithm

• Finds shortest paths from a single source.
• Works for graphs with negative weights (unlike Dijkstra’s).
• Detects negative cycles (if relaxation can still occur after V-1 iterations).
• Time complexity: O(VE)*.

When to Use:

• Khalti’s Inter-Bank Transfers: If banks have negative "rebate" fees, Khalti might use Bellman-Ford to find the cheapest path for fund transfers.

---

4. Topological Sorting

• Linear ordering of vertices such that for every directed edge u → v, u comes before v.
• Applications:
  • Course prerequisite scheduling (e.g., "Data Structures" must be taken before "Algorithms").
  • Task dependency resolution in project management.

Algorithm (Kahn’s):

1. Compute in-degree (number of incoming edges) for each vertex.
2. Enqueue all vertices with in-degree = 0.
3. While queue is not empty:
   • Dequeue a vertex, add it to the sorted list.
   • For each neighbor, decrement its in-degree. If in-degree becomes 0, enqueue it.
4. If sorted list has V vertices, topological sort exists; else, there’s a cycle.

Worked Example: Graph (Course Dependencies):

      A (Algorithms)
     /
    B (Data Structures)
   /
C (Discrete Math) → D (Computer Networks)

In-Degrees: A: 1, B: 1, C: 0, D: 1

Trace Table:

Topological Order: C → B → A → D

Real-World Use:

• TU Exam Schedule: Tribhuvan University uses topological sorting to schedule exams. For example, "Data Structures" (B) must be taken before "Algorithms" (A), and "Discrete Math" (C) before both.
• GitHub Dependency Installation: When you run pip install package, pip performs a topological sort to install dependencies in the correct order.

---

5. Advanced Applications

A. Network Flow Problems

• Max Flow Min Cut Theorem: The maximum flow through a network equals the capacity of the minimum cut.
• Applications:
  • Nepal’s Water Distribution: Optimizing pipe capacities to supply water to villages.
  • Ncell’s Data Routing: Maximizing data flow through cell towers.

B. Traveling Salesman Problem (TSP)

• Find the shortest possible route that visits each city exactly once and returns to the origin.
• NP-Hard (no known efficient solution for large graphs).
• Approximation Algorithms: Used by delivery companies like Daraz for route optimization.

---

In the Real World

1. Pathao’s Ride Matching:

   • Graph Idea: Drivers and riders are vertices; edges represent distances/availability.
   • Algorithm: Uses Dijkstra’s to find the nearest driver and BFS to explore nearby riders efficiently.
   • Impact: Reduces wait times by dynamically rerouting drivers based on real-time traffic (weighted by distance + estimated arrival time).

2. NTC’s Fiber-Optic Backbone:

   • Graph Idea: Cities are vertices; fiber cables are weighted edges (cost).
   • Algorithm: Kruskal’s MST connects all cities with minimal cable usage, saving millions in infrastructure costs.
   • Impact: Ensures reliable internet across Nepal without redundant connections.

3. Khalti’s Inter-Bank Transfers:

   • Graph Idea: Banks are vertices; edges are transfer routes with fees (some may have "negative" rebates).
   • Algorithm: Bellman-Ford finds the cheapest path for fund transfers, even with complex fee structures.
   • Impact: Users get the lowest transaction fees when sending money between banks.

4. Daraz’s Warehouse Network:

   • Graph Idea: Warehouses and delivery hubs are vertices; roads are weighted edges (distance + tolls).
   • Algorithm: Prim’s MST connects warehouses with minimal shipping costs, while Dijkstra’s optimizes individual delivery routes.
   • Impact: Faster deliveries and lower operational costs.

5. Nepal Electricity Authority (NEA) Grid:

   • Graph Idea: Power stations and substations are vertices; transmission lines are edges with capacity limits.
   • Algorithm: Max Flow ensures electricity is distributed efficiently without overloading any line.
   • Impact: Prevents blackouts during peak demand.

---

Exam Tip

1. Graph Representations:

   • Always label vertices and edges clearly in diagrams.
   • For adjacency matrices, show the 2D array with weights.
   • For adjacency lists, list neighbors explicitly.

2. Traversals (BFS/DFS):

   • Show the queue/stack state after each step in your answer.
   • Highlight the order of processing (e.g., "BFS order: A → B → C → D").
   • For DFS, mention whether you’re using recursion or a stack.

3. MST (Kruskal’s/Prim’s):

   • Sort edges first (for Kruskal’s) and show the sorted list.
   • Use Union-Find (Disjoint Set) for Kruskal’s to detect cycles efficiently.
   • For Prim’s, always start with a vertex and greedily add the cheapest edge from the MST to a vertex outside it.
   • Calculate the total weight of the MST in your answer.

4. Shortest Path (Dijkstra’s):

   • Initialize distances correctly (dist[source] = 0, others = ∞).
   • Show the priority queue updates at each step.
   • Highlight the relaxation step: dist[v] = min(dist[v], dist[u] + weight(u,v)).
   • For graphs with negative weights, mention Bellman-Ford and its ability to detect negative cycles.

5. Topological Sort:

   • Compute in-degrees first and show the initial queue.
   • Process vertices in order, updating in-degrees dynamically.
   • If the graph has a cycle, state that no topological order exists.

6. Common Pitfalls:

   • Forgetting to sort edges in Kruskal’s.
   • Not handling negative weights in Dijkstra’s (use Bellman-Ford instead).
   • Missing the base case in recursive DFS (e.g., no neighbors left).
   • Incorrect cycle detection in MST (always verify with Union-Find).

7. Diagrams Are Mandatory:

   • Draw the graph before applying any algorithm.
   • Show state after each step (e.g., queue in BFS, MST edges added in Kruskal’s).
   • Use arrows for directed graphs and labels for weights.

8. Real-World Connections:

   • NTC, NEA, and Khalti love MST and shortest path problems.
   • Pathao and Daraz use BFS/Dijkstra’s for routing.
   • TU exam scheduling is topological sorting in disguise!

---

Practice Questions (Exam-Style)

1. Draw the adjacency matrix and adjacency list for the following graph:

      A
    / | \
   B  C  D
   

   (Assume all edges are unweighted.)

2. Apply BFS and DFS on the above graph starting from vertex A. Show the traversal order and the queue/stack states at each step.

3. Find the MST of the following graph using Kruskal’s and Prim’s algorithms. Calculate the total weight.

      A
    /|\
   B C D
   / \  \
     E   F  G
   

   Weights: A-B=1, A-C=2, A-D=3, B-E=4, B-F=5, D-G=6, C-F=7.

4. Use Dijkstra’s algorithm to find the shortest paths from vertex A to all other vertices in the following graph:

      A
    / | \
   B(1)C(4)
    \   /
     \ /
      D(2,3)
   

   Show the distance table after each step.

5. Perform topological sorting on the following directed graph (course prerequisites):

      A (Algorithms)
     /
    B (Data Structures)
   /
   C (Discrete Math) → D (Computer Networks)
   

   Is a topological order possible? If yes, list one.

---

Code Example: BFS in Python

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    traversal_order = []

    while queue:
        vertex = queue.popleft()
        traversal_order.append(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return traversal_order

# Example graph (adjacency list)
graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'E'],
    'C': ['A', 'F'],
    'D': ['A'],
    'E': ['B'],
    'F': ['C']
}

print(bfs(graph, 'A'))  # Output: ['A', 'B', 'C', 'D', 'E', 'F']

Trace of BFS Execution:

---

Code Example: Kruskal’s Algorithm in Python

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * 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):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return False  # Already in the same set
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
        return True

def kruskal(graph, vertices):
    edges = sorted(graph['edges'], key=lambda x: x[2])
    uf = UnionFind(len(vertices))
    mst = []

    for edge in edges:
        u, v, weight = edge
        if uf.union(u, v):
            mst.append(edge)
            if len(mst) == len(vertices) - 1:
                break
    return mst

# Example graph
graph = {
    'vertices': ['A', 'B', 'C', 'D'],
    'edges': [
        (0, 1, 1),  # A-B: 1
        (0, 2, 2),  # A-C: 2
        (1, 2, 3),  # B-C: 3
        (1, 3, 4),  # B-D: 4
        (2, 3, 5)   # C-D: 5
    ]
}

mst = kruskal(graph, graph['vertices'])
print("MST Edges:", mst)  # Output: [(0, 1, 1), (0, 2, 2), (1, 3, 4)]

Trace of Kruskal’s Execution:

---

Final Checklist Before Exam

• Can you draw an adjacency matrix/list for any given graph?
• Can you apply BFS/DFS and show queue/stack states?
• Can you implement Kruskal’s/Prim’s and calculate MST weight?
• Can you run Dijkstra’s step-by-step with a priority queue?
• Can you detect cycles in a graph and explain topological sorting?
• Can you relate graphs to real-world problems (NTC, Pathao, Khalti)?