14. Graphs

14.1 Graph Basics

A graph G = (V, E) consists of a set of vertices V and a set of edges E that connect pairs of vertices. Graphs can be classified along several dimensions:

• Undirected vs. Directed (Digraph): In an undirected graph edges have no orientation; in a directed graph each edge (u, v) points from u to v.
• Weighted vs. Unweighted: Weighted graphs assign a numeric weight w(u, v) to each edge; unweighted graphs treat all edges as having weight 1 (or 0 for adjacency‑matrix convenience).
• Simple vs. Multigraph: Simple graphs contain at most one edge between any pair of vertices and no self‑loops. Multigraphs allow parallel edges and/or self‑loops.

Key Properties

• Degree: For an undirected vertex v, degree deg(v) is the number of incident edges. In a digraph we distinguish in‑degree (incoming edges) and out‑degree (outgoing edges).
• Path: A sequence of vertices v₀, v₁, …, vₖ such that each consecutive pair is an edge. A simple path repeats no vertices.
• Cycle: A path that starts and ends at the same vertex with length ≥ 2 (in undirected graphs) or ≥ 1 (in directed graphs).
• Connectedness: An undirected graph is connected if there exists a path between every pair of vertices. For digraphs we speak of strongly connected (reachability both ways) and weakly connected (connected when ignoring direction).
• Acyclic: A graph with no cycles. An acyclic undirected graph is a forest; a connected acyclic undirected graph is a tree. In digraphs, acyclic graphs are called DAGs.

14.2 Graph Representation

The choice of representation affects both memory usage and the efficiency of common operations.

Adjacency Matrix

A 2‑D array A[V][V] where A[i][j] stores the weight of edge (i, j) if it exists; otherwise a sentinel value (commonly ∞ for weighted graphs or 0 for unweighted).

Example (undirected, weighted) for vertices {0,1,2,3} with edges (0‑1,5), (1‑2,3), (2‑3,1):

   0  1  2  3
0  ∞  5  ∞  ∞
1  5  ∞  3  ∞
2  ∞  3  ∞  1
3  ∞  ∞  1  ∞

Adjacency List

An array adj[V] where each entry is a list of pairs (neighbor, weight). For the same graph:

0 → [(1,5)]
1 → [(0,5),(2,3)]
2 → [(1,3),(3,1)]
3 → [(2,1)]

Edge List

A simple array of tuples (u, v, w). Useful when algorithms need to sort edges (e.g., Kruskal’s MST).

14.3 Breadth‑First Search (BFS)

BFS explores vertices level‑by‑level using a FIFO queue. It yields the shortest path in terms of number of edges for unweighted graphs.

Algorithm

1. Mark the source vertex s as visited and enqueue it.
2. While the queue is not empty:
     a. Dequeue a vertex v.
     b. For each neighbor u of v, if u is unvisited, mark it visited and enqueue u.

Pseudocode

BFS(G, s):
    visited[s] = true
    Q.enqueue(s)
    while Q not empty:
        v = Q.dequeue()
        for each u in adj[v]:
            if not visited[u]:
                visited[u] = true
                Q.enqueue(u)

Complexity

Time: O(V + E) (each vertex enqueued/dequeued once, each edge examined once).
Space: O(V) for the visited array and the queue.

Applications

• Shortest path in unweighted graphs.
• Testing connectivity.
• Checking bipartiteness (assign alternating colors while traversing).

14.4 Depth‑First Search (DFS)

DFS dives deep along each branch before backtracking, implemented either recursively or with an explicit stack.

Algorithm (recursive)

1. Mark vertex v visited.
2. For each neighbor u of v, if u is unvisited, recursively call DFS(u).

Pseudocode

DFS(G, v):
    visited[v] = true
    for each u in adj[v]:
        if not visited[u]:
            DFS(G, u)

Iterative version

Replace the recursion with a stack: push the start vertex, then pop, visit, and push all unvisited neighbors.

Complexity

Time: O(V + E). Space: O(V) for the visited array plus the recursion/stack depth (worst‑case O(V)).

Applications

• Cycle detection (back edge to an ancestor in DFS tree).
• Topological sorting (post‑order).
• Finding strongly connected components (Kosaraju/Tarjan).
• Path finding and maze solving.

14.5 Shortest‑Path Algorithms

Dijkstra’s Algorithm (non‑negative weights)

Finds single‑source shortest paths from a source s to all vertices using a min‑priority queue.

Key Idea

Maintain a distance estimate dist[v]. Repeatedly extract the vertex with smallest tentative distance, relax its outgoing edges.

Relaxation

For edge (u, v) with weight w(u, v):

if dist[u] + w(u, v) < dist[v]:
    dist[v] = dist[u] + w(u, v)

Complexity

• Binary heap: O((V + E) log V).
• Array (simple implementation): O(V²).

Example

Graph edges: (0‑1,4), (0‑2,1), (2‑1,2), (1‑3,1), (2‑3,5). Starting from source 0:

• dist[0]=0
• Extract 0 → relax: dist[1]=4, dist[2]=1
• Extract 2 → relax: dist[2]+2=3 < dist[1]? yes → dist[1]=3; dist[2]+5=6 → dist[3]=6
• Extract 1 → relax: dist[1]+1=4 < dist[3]? yes → dist[3]=4
• Extract 3 → done.

Shortest path 0 → 2 → 1 → 3 with total cost 4.

Bellman‑Ford Algorithm (handles negative weights)

Iteratively relaxes all edges V‑1 times; after that, any further relaxation indicates a negative‑weight cycle.

Pseudocode

BellmanFord(G, s):
    dist[s] = 0; for each v ≠ s: dist[v] = ∞
    repeat V-1 times:
        for each (u, v, w) in E:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    // negative‑cycle detection
    for each (u, v, w) in E:
        if dist[u] + w < dist[v]:
            return "Negative cycle detected"
    return dist

Complexity

Time: O(V·E). Space: O(V).

Floyd‑Warshall Algorithm (all‑pairs shortest paths)

Dynamic programming formulation that considers intermediate vertices.

Recurrence

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Initialize dist[i][j] with edge weight (or ∞ if no edge) and dist[i][i] = 0. Iterate k from 0 to V‑1.
Complexity
Time: O(V³). Space: O(V²) (the distance matrix).

14.6 Minimum Spanning Tree (MST)
An MST of a connected, weighted undirected graph is a spanning tree (acyclic, connects all vertices) with minimum total edge weight.

Kruskal’s Algorithm

Sort all edges in non‑decreasing order of weight.
Initialize a disjoint‑set (Union‑Find) structure where each vertex is its own set.
Iterate over sorted edges; for each edge (u, v), if Find(u) ≠ Find(v), add the edge to the MST and union the two sets.
Stop when the MST contains V‑1 edges.

Complexity
Sorting: O(E log E). Union‑Find operations: O(E α(V)) ≈ O(E). Overall: O(E log E).
Example
Graph edges: (0‑1,1), (1‑2,2), (2‑3,3), (0‑3,4), (0‑2,5). Sorted order yields selected edges (0‑1,1), (1‑2,2), (2‑3,3). Total weight = 6.


Prim’s Algorithm

Start from an arbitrary vertex, mark it as part of the growing tree.
Maintain a min‑heap of edges crossing the cut (tree ↔ non‑tree).
Repeatedly extract the minimum‑weight edge (u, v) where u is in the tree and v is not; add v to the tree and insert all edges from v to non‑tree vertices into the heap.
Continue until all vertices are included.

Complexity
With binary heap: O(E log V). With Fibonacci heap: O(E + V log V).
Cut Property (informal)
For any cut of the graph, the lightest edge crossing that cut belongs to *some* MST.

14.7 Union‑Find (Disjoint Set Union – DSU)
DSU maintains a partition of a set into disjoint subsets and supports near‑constant‑time union and find operations.
Operations

MakeSet(x): creates a new set containing only x (parent[x] = x, rank[x] = 0).
Find(x): returns the representative (root) of the set containing x. With path compression, the tree is flattened.
Union(x, y): merges the sets containing x and y. Union by rank/size attaches the shorter tree under the taller one.

Pseudocode with Path Compression
Find(x):
    if parent[x] != x:
        parent[x] = Find(parent[x])
    return parent[x]

Union(x, y):
    rx = Find(x); ry = Find(y)
    if rx == ry: return
    if rank[rx] < rank[ry]:
        parent[rx] = ry
    elif rank[rx] > rank[ry]:
        parent[ry] = rx
    else:
        parent[ry] = rx
        rank[rx] += 1

Complexity
Amortized O(α(V)) per operation, where α is the inverse Ackermann function (practically ≤ 4).
Applications

Kruskal’s MST.
Cycle detection in undirected graphs.
Percolation, image segmentation, network connectivity.


14.8 Topological Sorting
Topological order exists only for Directed Acyclic Graphs (DAGs). It lists vertices such that for every directed edge (u, v), u appears before v.

Kahn’s Algorithm (BFS‑based)

Compute indegree of each vertex.
Enqueue all vertices with indegree 0.
While queue not empty:

  a. Dequeue v, output it.

  b. For each neighbor u of v, decrement indegree[u]; if it becomes 0, enqueue u.
If output size < V, a cycle exists.

Complexity
Time: O(V + E). Space: O(V).

DFS‑based Algorithm

Perform DFS; when a vertex finishes (all outgoing edges explored), push it onto a stack.
After DFS completes, pop vertices from the stack to obtain the topological order.

Example
DAG edges: (5→2,5→0,4→0,4→1,2→3,3→1). One valid topological order: 5, 4, 2, 3, 1, 0.


14.9 Applications
14.9.1 Google Maps – Shortest Path
The road network is modeled as a weighted graph (vertices = intersections, edges = road segments with travel time/distance). Dijkstra’s algorithm (or A* with heuristics) yields the fastest route.

14.9.2 Facebook Friends – Social Graph
Users are vertices; friendships are undirected edges. Friend‑suggestion scores often rely on mutual‑neighbor counts (triadic closure) – essentially counting length‑2 paths between non‑friends.

14.9.3 Airline Routes – Weighted Graph & Flow
Flight connections form a weighted graph (cost, time). Cheapest routes can be found with Dijkstra (non‑negative) or Bellman‑Ford (if negative costs like rebates appear). Crew scheduling and aircraft assignment are modeled as flow networks.

14.9.4 Computer Networks – Routing & Reliability

OSPF uses Dijkstra to compute shortest‑path trees from each router.
Network reliability (probability of staying connected) can be evaluated via min‑cut algorithms.
LAN topologies (star, bus, mesh) are represented as graphs for simulation and analysis.



This chapter equips you with the theoretical foundations and practical tools needed to model, traverse, optimize, and apply graph‑based solutions across a wide range of domains in computer science and information technology.