Part 7: Graph Theory and Algorithms

Part of the Mathematics for Programming 101 Series

The Deployment Failure That Taught Me Graph Theory

I was building a microservices deployment system. Services had dependencies—Service A needs B, B needs C, C needs D, etc.

My deployment script:

for service in services:
    deploy(service)

Deployments kept failing. Service A would start before its dependency B was ready. Random timeouts. Inconsistent behavior.

The problem: I was deploying in arbitrary order, not dependency order.

The solution: Topological sort—a graph algorithm.

def deploy_in_order(services, dependencies):
    """Deploy services in dependency order using topological sort"""
    graph = build_dependency_graph(services, dependencies)
    deployment_order = topological_sort(graph)
    
    for service in deployment_order:
        deploy(service)

Deployments became reliable. Every service deployed only after its dependencies were ready.

That's when I learned: Graph theory isn't academic—it's how we model and solve real-world dependency problems.

What is Graph Theory?

A graph is a collection of:

• Vertices (nodes): The entities

• Edges: Connections between entities

Graphs model:

• Social networks (people + friendships)

• Road networks (cities + highways)

• Dependencies (services + requirements)

• Web pages (pages + links)

• Data flow (components + connections)

from collections import defaultdict, deque

class Graph:
    """Basic graph data structure"""
    
    def __init__(self, directed=True):
        self.graph = defaultdict(list)
        self.directed = directed
    
    def add_edge(self, u, v, weight=1):
        """Add edge from u to v"""
        self.graph[u].append((v, weight))
        
        if not self.directed:
            self.graph[v].append((u, weight))
    
    def get_vertices(self):
        """Get all vertices"""
        vertices = set(self.graph.keys())
        for neighbors in self.graph.values():
            for v, _ in neighbors:
                vertices.add(v)
        return vertices
    
    def display(self):
        """Display graph structure"""
        for vertex in sorted(self.graph.keys()):
            neighbors = [f"{v}(w={w})" for v, w in self.graph[vertex]]
            print(f"{vertex} → {', '.join(neighbors)}")

# Example: Social network
social_graph = Graph(directed=False)
social_graph.add_edge("Alice", "Bob")
social_graph.add_edge("Alice", "Charlie")
social_graph.add_edge("Bob", "David")
social_graph.add_edge("Charlie", "David")
social_graph.add_edge("Charlie", "Eve")

print("Social Network Graph:")
social_graph.display()

Graph Representations

Adjacency List vs Adjacency Matrix

class GraphRepresentations:
    """Compare different graph representations"""
    
    @staticmethod
    def adjacency_list(edges):
        """
        Adjacency List: {vertex: [neighbors]}
        Space: O(V + E)
        Good for: Sparse graphs, iterating neighbors
        """
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
        return dict(graph)
    
    @staticmethod
    def adjacency_matrix(edges, n_vertices):
        """
        Adjacency Matrix: 2D array
        Space: O(V²)
        Good for: Dense graphs, checking if edge exists
        """
        matrix = [[0] * n_vertices for _ in range(n_vertices)]
        
        for u, v in edges:
            matrix[u][v] = 1
        
        return matrix
    
    @staticmethod
    def edge_list(edges):
        """
        Edge List: [(u, v), ...]
        Space: O(E)
        Good for: Algorithms that process edges
        """
        return edges

# Example
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]

adj_list = GraphRepresentations.adjacency_list(edges)
adj_matrix = GraphRepresentations.adjacency_matrix(edges, n_vertices=4)

print("Adjacency List:", adj_list)
print("\nAdjacency Matrix:")
for row in adj_matrix:
    print(row)

Graph Traversal Algorithms

Breadth-First Search (BFS)

Explores level by level—like ripples in water.

def bfs(graph, start):
    """
    Breadth-First Search
    Applications:
    - Shortest path in unweighted graph
    - Level-order traversal
    - Finding connected components
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    order = []
    
    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        
        # Visit all neighbors
        for neighbor, _ in graph.graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return order

# Example
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "E")
g.add_edge("D", "F")
g.add_edge("E", "F")

print("\nBFS Traversal from A:")
print(bfs(g, "A"))

Depth-First Search (DFS)

Explores as deep as possible before backtracking.

def dfs_recursive(graph, vertex, visited=None):
    """
    Depth-First Search (Recursive)
    Applications:
    - Detecting cycles
    - Topological sorting
    - Finding strongly connected components
    """
    if visited is None:
        visited = set()
    
    visited.add(vertex)
    order = [vertex]
    
    for neighbor, _ in graph.graph[vertex]:
        if neighbor not in visited:
            order.extend(dfs_recursive(graph, neighbor, visited))
    
    return order

def dfs_iterative(graph, start):
    """Depth-First Search (Iterative)"""
    visited = set()
    stack = [start]
    order = []
    
    while stack:
        vertex = stack.pop()
        
        if vertex not in visited:
            visited.add(vertex)
            order.append(vertex)
            
            # Add neighbors to stack
            for neighbor, _ in reversed(graph.graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return order

print("\nDFS Traversal from A (Recursive):")
print(dfs_recursive(g, "A"))

print("\nDFS Traversal from A (Iterative):")
print(dfs_iterative(g, "A"))

Shortest Path Algorithms

Dijkstra's Algorithm

Find shortest path in weighted graph (non-negative weights).

import heapq

def dijkstra(graph, start):
    """
    Dijkstra's shortest path algorithm
    
    Time: O((V + E) log V) with min-heap
    Returns: distances and paths from start to all vertices
    """
    # Initialize distances
    distances = {vertex: float('infinity') for vertex in graph.get_vertices()}
    distances[start] = 0
    
    # Track paths
    previous = {vertex: None for vertex in graph.get_vertices()}
    
    # Priority queue: (distance, vertex)
    pq = [(0, start)]
    visited = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current in visited:
            continue
        
        visited.add(current)
        
        # Check all neighbors
        for neighbor, weight in graph.graph[current]:
            distance = current_dist + weight
            
            # If shorter path found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current
                heapq.heappush(pq, (distance, neighbor))
    
    return distances, previous

def reconstruct_path(previous, start, end):
    """Reconstruct shortest path from start to end"""
    path = []
    current = end
    
    while current is not None:
        path.append(current)
        current = previous[current]
    
    path.reverse()
    
    if path[0] != start:
        return None  # No path exists
    
    return path

# Example: Road network
road_network = Graph(directed=False)
road_network.add_edge("A", "B", weight=4)
road_network.add_edge("A", "C", weight=2)
road_network.add_edge("B", "C", weight=1)
road_network.add_edge("B", "D", weight=5)
road_network.add_edge("C", "D", weight=8)
road_network.add_edge("C", "E", weight=10)
road_network.add_edge("D", "E", weight=2)

distances, previous = dijkstra(road_network, "A")

print("\nShortest distances from A:")
for vertex, dist in sorted(distances.items()):
    path = reconstruct_path(previous, "A", vertex)
    print(f"  {vertex}: {dist} via {' → '.join(path)}")

Bellman-Ford Algorithm

Handles negative weights (but not negative cycles).

def bellman_ford(graph, start):
    """
    Bellman-Ford algorithm
    
    Can handle negative weights
    Detects negative cycles
    Time: O(VE)
    """
    vertices = graph.get_vertices()
    distances = {v: float('infinity') for v in vertices}
    distances[start] = 0
    previous = {v: None for v in vertices}
    
    # Relax edges V-1 times
    for _ in range(len(vertices) - 1):
        for u in graph.graph:
            for v, weight in graph.graph[u]:
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight
                    previous[v] = u
    
    # Check for negative cycles
    for u in graph.graph:
        for v, weight in graph.graph[u]:
            if distances[u] + weight < distances[v]:
                raise ValueError("Graph contains negative cycle")
    
    return distances, previous

# Example with negative weight
weighted_graph = Graph(directed=True)
weighted_graph.add_edge("A", "B", weight=5)
weighted_graph.add_edge("A", "C", weight=2)
weighted_graph.add_edge("B", "D", weight=1)
weighted_graph.add_edge("C", "B", weight=-3)  # Negative weight
weighted_graph.add_edge("C", "D", weight=6)

distances, previous = bellman_ford(weighted_graph, "A")

print("\nBellman-Ford distances from A:")
for vertex, dist in sorted(distances.items()):
    if dist != float('infinity'):
        print(f"  {vertex}: {dist}")

Topological Sort (Dependency Resolution)

def topological_sort(graph):
    """
    Topological sort: Linear ordering of vertices
    such that for every edge u→v, u comes before v
    
    Applications:
    - Build systems (compile dependencies)
    - Package managers (install order)
    - Job scheduling
    """
    # Calculate in-degrees
    in_degree = defaultdict(int)
    vertices = graph.get_vertices()
    
    for v in vertices:
        in_degree[v] = 0
    
    for u in graph.graph:
        for v, _ in graph.graph[u]:
            in_degree[v] += 1
    
    # Start with vertices that have no dependencies
    queue = deque([v for v in vertices if in_degree[v] == 0])
    result = []
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        # Reduce in-degree of neighbors
        for neighbor, _ in graph.graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check for cycles
    if len(result) != len(vertices):
        raise ValueError("Graph has a cycle (no topological ordering possible)")
    
    return result

# Example: Build system dependencies
build_deps = Graph(directed=True)
build_deps.add_edge("main.c", "main.o")
build_deps.add_edge("utils.c", "utils.o")
build_deps.add_edge("main.o", "program")
build_deps.add_edge("utils.o", "program")

build_order = topological_sort(build_deps)
print("\nBuild order:")
for item in build_order:
    print(f"  {item}")

Real Application: Package Dependency Resolution

class PackageManager:
    """Simulate package manager dependency resolution"""
    
    def __init__(self):
        self.packages = Graph(directed=True)
    
    def add_package(self, package, dependencies=None):
        """Add package with its dependencies"""
        if dependencies:
            for dep in dependencies:
                self.packages.add_edge(dep, package)
    
    def install_order(self, package):
        """
        Determine installation order for a package
        Returns list of packages to install in order
        """
        # Find all dependencies (DFS)
        def collect_dependencies(pkg, visited=None):
            if visited is None:
                visited = set()
            
            if pkg in visited:
                return []
            
            visited.add(pkg)
            deps = []
            
            # Find packages that this package depends on
            for dep in self.packages.graph:
                for neighbor, _ in self.packages.graph[dep]:
                    if neighbor == pkg and dep not in visited:
                        deps.extend(collect_dependencies(dep, visited))
                        deps.append(dep)
            
            return deps
        
        dependencies = collect_dependencies(package)
        dependencies.append(package)
        
        # Remove duplicates while preserving order
        seen = set()
        result = []
        for pkg in dependencies:
            if pkg not in seen:
                seen.add(pkg)
                result.append(pkg)
        
        return result
    
    def detect_circular_dependency(self):
        """Detect if there are circular dependencies"""
        try:
            topological_sort(self.packages)
            return False
        except ValueError:
            return True

# Example
pm = PackageManager()
pm.add_package("app", dependencies=["framework", "utils"])
pm.add_package("framework", dependencies=["core"])
pm.add_package("utils", dependencies=["core"])
pm.add_package("core", dependencies=[])

print("\nPackage Installation Order:")
install_order = pm.install_order("app")
for i, pkg in enumerate(install_order, 1):
    print(f"  {i}. {pkg}")

print(f"\nCircular dependencies? {pm.detect_circular_dependency()}")

Minimum Spanning Tree

Connect all vertices with minimum total edge weight.

Prim's Algorithm

def prims_mst(graph):
    """
    Prim's algorithm for Minimum Spanning Tree
    
    Time: O(E log V)
    Returns: MST edges and total weight
    """
    vertices = graph.get_vertices()
    start = list(vertices)[0]
    
    visited = {start}
    edges = []
    total_weight = 0
    
    # Priority queue: (weight, u, v)
    pq = [(w, start, v) for v, w in graph.graph[start]]
    heapq.heapify(pq)
    
    while pq and len(visited) < len(vertices):
        weight, u, v = heapq.heappop(pq)
        
        if v in visited:
            continue
        
        # Add edge to MST
        visited.add(v)
        edges.append((u, v, weight))
        total_weight += weight
        
        # Add new edges to priority queue
        for neighbor, w in graph.graph[v]:
            if neighbor not in visited:
                heapq.heappush(pq, (w, v, neighbor))
    
    return edges, total_weight

# Example: Network cable installation
network = Graph(directed=False)
network.add_edge("A", "B", weight=4)
network.add_edge("A", "C", weight=2)
network.add_edge("B", "C", weight=1)
network.add_edge("B", "D", weight=5)
network.add_edge("C", "D", weight=8)
network.add_edge("C", "E", weight=10)
network.add_edge("D", "E", weight=2)

mst_edges, mst_weight = prims_mst(network)

print("\nMinimum Spanning Tree (Prim's):")
for u, v, w in mst_edges:
    print(f"  {u} — {v} (weight: {w})")
print(f"Total weight: {mst_weight}")

Cycle Detection

def has_cycle_directed(graph):
    """Detect cycle in directed graph using DFS"""
    vertices = graph.get_vertices()
    visited = set()
    rec_stack = set()  # Recursion stack
    
    def dfs(v):
        visited.add(v)
        rec_stack.add(v)
        
        for neighbor, _ in graph.graph[v]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True  # Back edge found = cycle
        
        rec_stack.remove(v)
        return False
    
    for vertex in vertices:
        if vertex not in visited:
            if dfs(vertex):
                return True
    
    return False

def has_cycle_undirected(graph):
    """Detect cycle in undirected graph using DFS"""
    vertices = graph.get_vertices()
    visited = set()
    
    def dfs(v, parent):
        visited.add(v)
        
        for neighbor, _ in graph.graph[v]:
            if neighbor not in visited:
                if dfs(neighbor, v):
                    return True
            elif neighbor != parent:
                return True  # Cycle found
        
        return False
    
    for vertex in vertices:
        if vertex not in visited:
            if dfs(vertex, None):
                return True
    
    return False

# Test cycle detection
cyclic_graph = Graph(directed=True)
cyclic_graph.add_edge("A", "B")
cyclic_graph.add_edge("B", "C")
cyclic_graph.add_edge("C", "A")  # Creates cycle

print(f"\nCycle in directed graph? {has_cycle_directed(cyclic_graph)}")

acyclic_graph = Graph(directed=True)
acyclic_graph.add_edge("A", "B")
acyclic_graph.add_edge("B", "C")
acyclic_graph.add_edge("A", "C")

print(f"Cycle in acyclic graph? {has_cycle_directed(acyclic_graph)}")

Real Application: Social Network Analysis

class SocialNetwork:
    """Model social network using graph"""
    
    def __init__(self):
        self.graph = Graph(directed=False)
    
    def add_friendship(self, person1, person2):
        """Add friendship connection"""
        self.graph.add_edge(person1, person2)
    
    def mutual_friends(self, person1, person2):
        """Find mutual friends between two people"""
        friends1 = {v for v, _ in self.graph.graph[person1]}
        friends2 = {v for v, _ in self.graph.graph[person2]}
        return friends1 & friends2
    
    def degrees_of_separation(self, person1, person2):
        """
        Find degrees of separation (shortest path)
        Uses BFS
        """
        if person1 == person2:
            return 0
        
        visited = {person1}
        queue = deque([(person1, 0)])
        
        while queue:
            current, distance = queue.popleft()
            
            for neighbor, _ in self.graph.graph[current]:
                if neighbor == person2:
                    return distance + 1
                
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, distance + 1))
        
        return None  # Not connected
    
    def suggest_friends(self, person, max_suggestions=5):
        """
        Suggest friends (friends of friends not already friends)
        """
        # Get current friends
        friends = {v for v, _ in self.graph.graph[person]}
        friends.add(person)
        
        # Count mutual friend connections
        suggestions = defaultdict(int)
        
        for friend in list(self.graph.graph[person]):
            friend_name = friend[0]
            for fof, _ in self.graph.graph[friend_name]:
                if fof not in friends:
                    suggestions[fof] += 1
        
        # Sort by number of mutual friends
        sorted_suggestions = sorted(suggestions.items(), 
                                   key=lambda x: x[1], 
                                   reverse=True)
        
        return sorted_suggestions[:max_suggestions]

# Example
sn = SocialNetwork()
sn.add_friendship("Alice", "Bob")
sn.add_friendship("Alice", "Charlie")
sn.add_friendship("Bob", "David")
sn.add_friendship("Charlie", "David")
sn.add_friendship("Charlie", "Eve")
sn.add_friendship("David", "Frank")
sn.add_friendship("Eve", "Frank")

print("\nSocial Network Analysis:")
print(f"Mutual friends (Alice, David): {sn.mutual_friends('Alice', 'David')}")
print(f"Degrees of separation (Alice, Frank): {sn.degrees_of_separation('Alice', 'Frank')}")

suggestions = sn.suggest_friends("Alice")
print(f"\nFriend suggestions for Alice:")
for person, mutual_count in suggestions:
    print(f"  {person} ({mutual_count} mutual friends)")

Key Takeaways

• Graphs model relationships between entities in real systems

• BFS finds shortest paths in unweighted graphs

• DFS explores deeply and detects cycles

• Dijkstra's algorithm finds shortest paths with weights

• Topological sort resolves dependencies correctly

• MST algorithms minimize connection costs

• Graph theory appears everywhere: networks, dependencies, social systems, routing, scheduling

Series Conclusion

You've now completed the Mathematics for Programming 101 series! You've learned:

1. Why mathematics matters in real programming work

2. Linear algebra for data transformations and ML

3. Calculus for optimization and training models

4. Probability and statistics for decision-making

5. Discrete mathematics for algorithms and data structures

6. Number theory for cryptography and security

7. Graph theory for modeling and solving network problems

Remember: Mathematics isn't about memorizing formulas. It's about:

• Building intuition through practice

• Solving real problems systematically

• Making better engineering decisions

• Understanding why things work

Keep exploring. Keep building. Keep learning.

---

Navigation

• ← Part 6: Number Theory and Cryptography

• Back to Series Overview

• Back to Programming Section