Graph Theory & Networks

Graphs model networks of all kinds. Learn vertices and edges, directed, undirected and weighted graphs, degree, paths, cycles and connectivity, trees and spanning trees (Kruskal, Prim), shortest paths (Dijkstra), topological sorting, and network flow (max-flow/min-cut) — with a Python Dijkstra implementation.

Road networks, power grids, communication routers, PCB nets, project task dependencies and social networks are graphs. Graph algorithms find shortest routes, cheapest cable layouts and bottlenecks.

An analogy

A graph is a map of cities (vertices) and roads (edges); weights are the travel times on each road.

Terminology

Directed vs undirected, weighted vs unweighted, simple graphs, degree, adjacency matrix/list representations. Paths visit vertices; cycles return to the start; connected graphs have a path between every pair.

Trees and spanning trees

Trees are minimally connected. A minimum spanning tree (Kruskal: add cheapest edges without cycles; Prim: grow from a vertex) connects all sites with least total cable/pipe length.

Shortest paths and ordering

Dijkstra (non-negative weights) for routing; Bellman–Ford handles negative weights; BFS for unweighted graphs. Topological sort orders tasks in a DAG (build systems, project schedules).

Flows and matching

Max-flow algorithms (Ford–Fulkerson, Edmonds–Karp) find network capacity and bottlenecks (min cut) — for traffic, pipelines, data networks. Bipartite matching assigns jobs to machines.

Formulas

Worked example: Shortest route

Given: Graph above, source A

Find: Shortest time A → F.

Answer: A → C → B → D → E → F, 12 min

Worked example: Minimum spanning tree

Given: Same edges as an undirected cable network

Find: MST weight.

Answer: Total 12 (5 edges for 6 vertices)

Dijkstra's shortest paths (Python)

import heapq

# Directed road/network graph: travel times in minutes
G = {
    "A": {"B": 4, "C": 2},
    "B": {"C": 1, "D": 5},
    "C": {"B": 1, "D": 8, "E": 10},
    "D": {"E": 2, "F": 6},
    "E": {"F": 2},
    "F": {},
}

def dijkstra(src):
    dist = {v: float("inf") for v in G}
    prev = {}
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                      # stale queue entry
        for v, w in G[u].items():
            if d + w < dist[v]:
                dist[v], prev[v] = d + w, u
                heapq.heappush(pq, (dist[v], v))
    return dist, prev

dist, prev = dijkstra("A")
path, node = [], "F"
while node != "A":
    path.append(node); node = prev[node]
print("distances:", dist)
print("shortest A->F:", " -> ".join(["A"] + path[::-1]), f"({dist['F']} min)")
# distances: {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 12}
# shortest A->F: A -> C -> B -> D -> E -> F (12 min)

A priority queue always expands the closest unvisited vertex; with non-negative weights each vertex's distance is final when popped. Note the shortest route to B goes through C (2 + 1 < 4).

Common mistakes

Applications

Key takeaways

Going further