Graph Algorithms: Paths, Trees, Shortest Paths & Network Flows

What is a Graph?

A graph is a non-linear data structure consisting of vertices (nodes) connected by edges (links). Graphs can be:

• Directed (edges have direction, e.g., one-way roads).
• Undirected (edges have no direction, e.g., friendships on social media).
• Weighted (edges have values, e.g., distances or costs).
• Unweighted (edges have no values, e.g., simple connections).

Graph Representations

Graphs are stored in memory using two primary methods:

1. Adjacency Matrix: A 2D array where matrix[i][j] = 1 if there’s an edge from vertex i to j.
2. Adjacency List: An array of linked lists where each index holds edges connected to that vertex.

graph TD
    A["Adjacency Matrix"] -->|"Space: O(V²)"| B["Dense graphs"]
    A -->|"Time: O(1) for edge check"| B
    C["Adjacency List"] -->|"Space: O(V+E)"| D["Sparse graphs"]
    C -->|"Time: O(V) for edge check"| D

Example: Represent the following graph using both methods:

A --3--> B --1--> C
|         /     |
1        4       2
|       /       |
D --2--> E

Adjacency Matrix:

   A B C D E
A [0,3,0,1,0]
B [0,0,1,0,4]
C [0,0,0,0,2]
D [2,0,0,0,0]
E [0,0,0,0,0]

Adjacency List:

A: [(B,3), (D,1)]
B: [(C,1), (E,4)]
C: [(E,2)]
D: [(A,2)]
E: []

Graph Traversal Algorithms

Traversal visits all vertices in a graph systematically. Two key algorithms:

1. Breadth-First Search (BFS)

• Uses a queue to explore vertices level by level.
• Applications: Shortest path in unweighted graphs, web crawling, social network analysis.

Algorithm Steps:

1. Start at the root node, enqueue it.
2. Dequeue a node, visit it, and enqueue all its unvisited neighbors.
3. Repeat until the queue is empty.

flowchart TD
    A["Start: Queue = [A]"] --> B["Dequeue A, visit A\nQueue = [B, D]"]
    B --> C["Dequeue B, visit B\nQueue = [D, C, E]"]
    C --> D["Dequeue D, visit D\nQueue = [C, E]"]
    D --> E["Dequeue C, visit C\nQueue = [E]"]
    E --> F["Dequeue E, visit E\nQueue = []\nDone"]

Code (Python):

from collections import deque

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

Trace for the above graph (BFS starting at A):

2. Depth-First Search (DFS)

• Uses a stack (or recursion) to explore as far as possible along each branch.
• Applications: Topological sorting, maze solving, detecting cycles.

Algorithm Steps:

1. Start at the root node, push it onto the stack.
2. Pop a node, visit it, and push its unvisited neighbors onto the stack.
3. Repeat until the stack is empty.

flowchart TD
    A["Start: Stack = [A]"] --> B["Pop A, visit A\nStack = [D, B]"]
    B --> C["Pop B, visit B\nStack = [D, C, E]"]
    C --> D["Pop E, visit E\nStack = [D, C]"]
    D --> E["Pop C, visit C\nStack = [D]"]
    E --> F["Pop D, visit D\nStack = []\nDone"]

Code (Python):

def DFS(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex, end=" ")
            visited.add(vertex)
            for neighbor in reversed(graph[vertex]):  # Reverse to visit in order
                if neighbor not in visited:
                    stack.append(neighbor)

Trace for the above graph (DFS starting at A):

Minimum Spanning Tree (MST)

An MST connects all vertices with the minimum total edge weight and no cycles. Two algorithms:

1. Prim’s Algorithm

• Greedily adds the cheapest edge from the current MST to a vertex outside it.
• Time Complexity: $O(E\log V)$ with a priority queue.

Steps for the graph:

A --3--> B --1--> C
|         /     |
1        4       2
|       /       |
D --2--> E

1. Start at A. Add edges A-B (3) and A-D (1). Choose A-D (cheaper).
2. Add edges D-E (2) and B-C (1). Choose B-C.
3. Add E-C (2). All vertices connected.

graph TD
    A["Step 1: Start at A\nMST: {A}"] --> B["Add A-D (1)\nMST: {A, D}"]
    B --> C["Add B-C (1)\nMST: {A, D, B, C}"]
    C --> D["Add E-C (2)\nMST: {A, D, B, C, E}\nDone"]

Code (Python):

import heapq

def prim(graph, start):
    mst = set([start])
    edges = [(cost, start, neighbor) for neighbor, cost in graph[start]]
    heapq.heapify(edges)
    while edges and len(mst) < len(graph):
        cost, u, v = heapq.heappop(edges)
        if v not in mst:
            mst.add(v)
            for neighbor, c in graph[v]:
                if neighbor not in mst:
                    heapq.heappush(edges, (c, v, neighbor))
    return mst

Trace:

2. Kruskal’s Algorithm

• Sorts all edges by weight and adds them to the MST if they don’t form a cycle.
• Time Complexity: $O(E\log E)$ (due to sorting).

Steps:

1. Sort edges: [(A,D,1), (B,C,1), (E,C,2), (A,B,3), (B,E,4)].
2. Add A-D (1), B-C (1), E-C (2). Skip A-B (cycle) and B-E (cycle).

graph TD
    A["Step 1: Sort edges\nEdges: [(A,D,1), (B,C,1), (E,C,2), (A,B,3), (B,E,4)]"] --> B["Add A-D (1)\nMST: {A, D}"]
    B --> C["Add B-C (1)\nMST: {A, D, B, C}"]
    C --> D["Add E-C (2)\nMST: {A, D, B, C, E}\nDone"]

Comparison of Prim and Kruskal:

Shortest Path Algorithms

1. Dijkstra’s Algorithm

• Finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edges.
• Time Complexity: $O((V+E)\log V)$ with a priority queue.

Steps for the graph (find shortest path from A):

1. Initialize distances: A=0, B=∞, C=∞, D=∞, E=∞.
2. Update neighbors of A: B=3, D=1.
3. Pick D (smallest distance). Update E via D: E=min(∞, 1+2)=3.
4. Pick B. Update C via B: C=min(∞, 3+1)=4.
5. Pick E. Update C via E: C=min(4, 3+2)=4 (no change).
6. Pick C. Done.

graph TD
    A["Step 1: Distances = {A:0, B:∞, C:∞, D:∞, E:∞}"] --> B["Update B=3, D=1\nDistances = {A:0, B:3, D:1}"]
    B --> C["Pick D (smallest)\nUpdate E=3\nDistances = {A:0, B:3, D:1, E:3}"]
    C --> D["Pick B\nUpdate C=4\nDistances = {A:0, B:3, D:1, E:3, C:4}"]
    D --> E["Pick E\nNo update\nDistances = {A:0, B:3, D:1, E:3, C:4}\nDone"]

Code (Python):

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

Trace:

2. Floyd-Warshall Algorithm

• Finds the shortest path between all pairs of vertices in a graph (even with negative weights).
• Time Complexity: $O(V^3)$.

Steps:

1. Initialize distance matrix dist[i][j] as the weight of edge (i,j) or ∞ if no edge.
2. For each intermediate vertex k, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

Example Graph:

A --3--> B --1--> C
|         /     |
1        4       2
|       /       |
D --2--> E

Initial Distance Matrix:

   A B C D E
A [0,3,∞,1,∞]
B [3,0,1,∞,4]
C [∞,1,0,∞,2]
D [1,∞,∞,0,2]
E [∞,4,2,2,0]

After k=A:

   A B C D E
A [0,3,∞,1,∞]
B [3,0,1,1,4]  (B->D via A: 3+1=4 > 1? No, keep 1)
C [∞,1,0,∞,2]
D [1,∞,∞,0,2]
E [∞,4,2,2,0]

After k=B:

   A B C D E
A [0,3,4,1,5]  (A->C via B: 3+1=4)
B [3,0,1,1,4]
C [4,1,0,1,2]  (C->D via B: 1+1=2 < ∞)
D [1,∞,∞,0,2]
E [5,4,2,2,0]  (E->A via B: 4+3=7 > 5? No)

Final Matrix:

   A B C D E
A [0,3,4,1,5]
B [3,0,1,1,4]
C [4,1,0,1,2]
D [1,4,5,0,2]
E [5,4,2,2,0]

Code (Python):

def floyd_warshall(graph):
    dist = [row[:] for row in graph]
    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

Network Flow: Ford-Fulkerson Algorithm

Used to find the maximum flow in a flow network (e.g., traffic, water pipes, data packets). Key Terms:

• Source (S): Starting point of flow.
• Sink (T): Ending point of flow.
• Residual Graph: Remaining capacity after assigning flow.

Example: Find max flow from S to T in this network:

S --4--> A --2--> T
|         /
3        3
|       /
D --5--> T

Steps:

1. Find an augmenting path (S->A->T) with bottleneck capacity 2. Update residual graph.
2. Find another path (S->D->T) with bottleneck 3. Update residual graph.
3. No more augmenting paths. Max flow = 2 + 3 = 5.

graph TD
    A["Step 1: Path S->A->T\nBottleneck: 2\nFlow: 2"] --> B["Update residual graph\nResidual: S-A=2, A-T=0"]
    B --> C["Step 2: Path S->D->T\nBottleneck: 3\nFlow: 3"] --> D["Update residual graph\nResidual: S-D=2, D-T=0"]
    D --> E["No more paths\nMax Flow = 5"]

Code (Python):

from collections import defaultdict

def ford_fulkerson(graph, source, sink):
    parent = [-1] * len(graph)
    max_flow = 0
    while bfs(graph, source, sink, parent):
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, graph[u][v])
            v = u
        max_flow += path_flow
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = u
    return max_flow

def bfs(graph, source, sink, parent):
    visited = [False] * len(graph)
    queue = [source]
    visited[source] = True
    while queue:
        u = queue.pop(0)
        for v in range(len(graph)):
            if not visited[v] and graph[u][v] > 0:
                parent[v] = u
                if v == sink:
                    return True
                queue.append(v)
                visited[v] = True
    return False

Trace:

In the Real World

Graph algorithms power many systems Nepalese students interact with daily:

1. Pathao/Daraz Delivery Routes

   • Algorithm Used: Dijkstra’s or A* (for shortest path).
   • How: When you order food or a product, the app calculates the fastest route from the restaurant/delivery center to your location using a weighted graph where:
     • Vertices = intersections or landmarks.
     • Edges = roads with weights = travel time (accounting for traffic, distance, and speed limits).
   • Example: If you order from a restaurant in Thapathali to your home in Koteshwor, the app might choose:
     • Route 1: Thapathali → Ring Road → Sano Chok → Koteshwor (15 mins).
     • Route 2: Thapathali → Putalisadak → Koteshwor (20 mins, but avoids Ring Road traffic). The graph dynamically updates edge weights based on real-time traffic data (from GPS sensors in Pathao’s fleet).

2. NTC’s Internet Routing

   • Algorithm Used: Shortest Path First (SPF) or Open Shortest Path First (OSPF), which are based on Dijkstra’s.
   • How: NTC’s network routers use graphs to forward data packets efficiently. Each router maintains a link-state database (a graph where vertices = routers, edges = network links with latency/cost weights). When you load a YouTube video, your request hops through routers via the shortest path in this graph.
   • Example: If you’re in Pokhara streaming a video hosted in Kathmandu, the path might be: Pokhara Router → Dhulikhel Router → Kathmandu Router → YouTube Server. The weights on edges could represent latency (e.g., Dhulikhel-Kathmandu link has higher weight due to congestion).

3. Khalti/E-Sewa Transaction Networks

   • Algorithm Used: Maximum Flow (Ford-Fulkerson) for load balancing.
   • How: When millions of users transact simultaneously (e.g., during Dashain or Tihar), Khalti’s servers use flow networks to distribute transactions across multiple processing nodes. The graph models:
     • Vertices = servers or processing units.
     • Edges = communication links with capacity = max transactions/second.
     • Source = user requests, Sink = completed transactions.
   • Example: During a sale, if 10,000 users try to pay via Khalti, the system routes requests to avoid overloading a single server. If Server A can handle 3,000 transactions/sec and Server B can handle 5,000, the max flow algorithm ensures no single server is overwhelmed.

4. Nepal Electricity Authority (NEA) Power Grid

   • Algorithm Used: Minimum Spanning Tree (Kruskal’s) for network reliability.
   • How: NEA uses MST to design power distribution networks that connect all substations with minimal wiring cost while ensuring no single failure disconnects the entire grid. For example:
     • Vertices = substations in Kathmandu, Pokhara, Biratnagar.
     • Edges = power lines with weights = cost or distance.
     • Kruskal’s algorithm selects the cheapest lines that connect all substations without cycles, ensuring redundancy.

5. WhatsApp Group Chats (Flooding Algorithm)

   • Algorithm Used: Breadth-First Search (BFS) for message propagation.
   • How: When you send a message in a large WhatsApp group, the app uses a graph where:
     • Vertices = users or servers.
     • Edges = message forwarding links.
     • BFS ensures the message reaches all users efficiently. If a user is offline, the message is stored and delivered later (like a queue in BFS).

Exam Tip

Graph algorithms are highly visual and often tested with:

1. Step-by-step traces: You’ll be asked to show how Dijkstra’s or Prim’s works on a given graph. Always:
   • Draw the graph.
   • Show the priority queue/adjacency list state after each step.
   • Highlight the chosen edge/vertex at each iteration.
2. Pseudocode + time complexity: Expect questions like:
   • “Write Dijkstra’s algorithm and analyze its time complexity for a graph with $V$ vertices and $E$ edges.”
   • Answer: Use a priority queue → $O((V+E)\log V)$.
3. Real-world mapping: Questions may ask you to model scenarios as graphs, e.g.:
   • “Represent Kathmandu’s traffic routes as a graph and find the shortest path from Thamel to Nagarjuna using Dijkstra’s.”
   • Tip: Assume edge weights = distance or time, and draw the graph clearly.
4. Shortcuts and pitfalls:
   • Dijkstra’s fails with negative weights: Use Bellman-Ford instead.
   • Prim’s vs. Kruskal’s: Prim’s is better for dense graphs; Kruskal’s for sparse.
   • BFS vs. DFS: BFS finds shortest paths in unweighted graphs; DFS is better for topological sorting.
5. Common mistakes to avoid:
   • Forgetting to update the residual graph in Ford-Fulkerson.
   • Not handling disconnected vertices in MST algorithms.
   • Misapplying adjacency matrix/list (e.g., using matrix for sparse graphs wastes space).

Practice Tip: For every algorithm, trace it on a small graph (4–5 vertices) and compare your steps with the textbook. Graphs are all about visualization—sketch the graph and annotate changes at each step!