DSA Graphs

Graphs

Maps needs cities and roads. A social feed needs people and follows. A build tool needs packages and import edges. Those are the same abstract object: a with stated edge meaning.

Before coding BFS, Dijkstra, or DSU, pin down , , and connectivity. The wrong contract makes a correct algorithm answer the wrong question.

Decision panel

Edge semantics

Directed? Weighted? Simple? Mutable?

Question type

Reachability, components, shortest path, order, cut…

List for sparse walks; matrix for dense pair tests.

Isolates

V includes degree-zero vertices; do not drop them.

What actually happens

Naive idea: jump into an algorithm because the problem “looks like a graph.” You may run undirected BFS on a directed follow graph, or minimize hops when the cost is travel time.

Better idea: write G = (V, E) with edge semantics, then pick the tool. Reachability and need traversal or DSU; hop distance needs BFS; non-negative weights need Dijkstra.

The improved design still fails when isolates are omitted from V, when multi-edges or self-loops were illegal but accepted, or when a matrix of size V² is allocated for a sparse social graph with V = 10⁷.

Invariant

Algorithms assume a fixed edge contract for the whole run: orientation, weight meaning, and which endpoints exist in V. Undirected storage must keep both adjacency entries consistent; directed storage must not invent reverse edges.

How to choose a graph approach

1. What is the objective? Hops, total weight, ordering, connectivity, flow, and matching are different problems.

2. Sparse or dense? |E| ≈ |V| favors lists; |E| ≈ |V|² can favor a matrix for pair queries.

3. Explicit or implicit? Grids and lock puzzles are graphs even when no adjacency list is given.

Quantitative check

Handshaking: undirected Σ deg(v) = 2|E|. An adjacency list therefore stores about 2|E| neighbor entries. At V = 10⁵ and E = 10⁵, list space is fine; a V×V boolean matrix wants ~10¹⁰ cells and will not fit.

Foundation

The graph contract: G = (V, E)

A graph is a set of vertices V plus a set (or multiset) of edges E. Before choosing an algorithm, state the edge semantics precisely. In an undirected graph {u, v} has no orientation; in a directed graph(u, v) means only u → v. A weight may represent distance, latency, price, capacity, or even a probability, and those meanings determine which operations are valid.

Reachability

Can a path from s reach t? Direction matters; weight usually does not.

Connectivity

Undirected components differ from directed weak/strong components.

Optimization

Minimum hops, minimum total weight, maximum flow, or minimum cut are different objectives.

Ordering

Prerequisites form a directed graph; a valid schedule exists only when it is acyclic.

Habit: ask whether the graph is directed, weighted, connected, simple, mutable, and explicitly supplied. A matrix or grid is an implicit graph; states in a lock puzzle are vertices even when no adjacency list appears in the problem statement.

Interactive graph foundations lab

Toggle orientation and representation, then compare that same graph under BFS, DFS, and cycle detection. The invariant panel is the sentence you should be able to defend for the algorithm you chose.

Interactive invariant lab

Graph state, not just graph shape

Switch semantics and algorithms, then step through the frontier, discovery state, and edge-level proof obligation.

Semantic contract

Undirected weighted graph

Each logical edge is listed in both endpoint buckets, but still counts once in |E|.

Invariant

For every logical edge {u, v}, v appears in adj[u] and u appears in adj[v].

Same graph, different physical layout

Weights are stored beside the destination; ∞ means no edge.

A→B(4), C(2)

B→A(4), D(3)

C→A(2), D(1), E(5)

D→B(3), C(1), E(2), G(6)

E→C(5), D(2), F(1)

F→E(1)

G→D(6)

ActiveFrontierProcessed

Edge-count identities and structural invariants

Fast facts that turn graph descriptions into proofs and complexity bounds.
Structure	Invariant	Consequence
Undirected graph	Σ deg(v) = 2\|E\|	An adjacency list stores each logical edge twice.
Directed graph	Σ indeg(v) = Σ outdeg(v) = \|E\|	Kahn's algorithm consumes every edge exactly once.
Undirected tree	connected and \|E\| = \|V\| − 1	Any extra edge creates a cycle; removing any edge disconnects it.
DAG	At least one zero-indegree vertex exists	Repeated removal yields a topological order.
Bipartite graph	No odd-length cycle	Two-color with BFS/DFS; a same-color edge is a certificate of failure.

A type-safe weighted edge model

Keep edge direction and weight explicit. For undirected graphs, call the helper twice; this prevents the most common representation bug from being hidden inside every algorithm.

Python

python

from dataclasses import dataclass

@dataclass(frozen=True)
class Edge:
    to: int
    weight: int

def add_directed(adj: list[list[Edge]], u: int, v: int, w: int) -> None:
    adj[u].append(Edge(v, w))

def add_undirected(adj: list[list[Edge]], u: int, v: int, w: int) -> None:
    add_directed(adj, u, v, w)
    add_directed(adj, v, u, w)

Java

java

import java.util.*;

final class WeightedGraphModel {
    record Edge(int to, int weight) {}

    static void addDirected(
            List<List<Edge>> adj, int u, int v, int w) {
        adj.get(u).add(new Edge(v, w));
    }

    static void addUndirected(
            List<List<Edge>> adj, int u, int v, int w) {
        addDirected(adj, u, v, w);
        addDirected(adj, v, u, w);
    }
}

Flow networks

In a Flow Network, edges have a Capacity. We want to find theMaximum Flow from a Source (S) to a Sink (T).

Ford-Fulkerson (DFS)

Finds "Augmenting Paths" until no more flow can be pushed. Uses a Residual Graph to allow flow to be "pushed back" if needed.

Dinic's Algorithm (BFS+DFS)

Uses a Level Graph to find multiple augmenting paths simultaneously. The gold standard for O(V²E) performance.

Max-Flow Min-Cut Theorem:

The maximum flow in a network is exactly equal to the capacity of the minimum cut that separates S and T.

Bipartite matching

The Assignment Problem

How do you match M Job Seekers to N Openings such that the maximum number of people are hired? This is a Max Bipartite Matching problem.

User 1

User 2

<->

Server A

Server B

Hopcroft-Karp Algorithm: O(E√V) performance for bipartite graphs.

Advanced connectivity

Articulation Points

A vertex whose removal increases the number of connected components. In network engineering, these are Single Points of Failure (SPOF).

Strongly Connected (SCC)

In a directed graph, an SCC is a set where every node is reachable from every other node.Tarjan's Algorithm finds all SCCs in a single pass (O(V+E)).

Formal vocabulary

Graph types

Directed vs undirected: edge (u,v) may or may not imply (v,u).
Weighted: edges carry cost, capacity, latency, or probability.
Self-loops / multi-edges: allowed or not changes definitions of trees and simple paths.
Tree: connected acyclic undirected graph; rooted trees add parent/child direction.

Degrees & density

For undirected graphs, |E| ≤ V(V−1)/2. When |E| ≈ |V| the graph is sparse (adjacency list wins); when |E| ≈ |V|² it is dense (matrix can be competitive for all-pairs checks).

Walks, trails, paths

Walk: any vertex sequence with consecutive edges (vertices may repeat).
Trail: walk with distinct edges (vertices may still repeat).
Simple path: all vertices distinct, what shortest-path algorithms usually return when ties are broken.

Eulerian trails vs Hamiltonian paths are different existence questions; do not confuse "visit every edge once" with "visit every vertex once".

Connectedness is not one concept

Undirected component

Every pair in the component is joined by a path. One BFS/DFS labels one component; an outer loop labels the whole graph.

Weakly connected

A directed graph becomes connected only after ignoring arrow direction. This says nothing about mutual reachability.

Strongly connected

For every u and v, both u ⇝ v and v ⇝ u exist. Contracting SCCs always produces a DAG.

Never lose isolated vertices: V is not merely “the endpoints seen in E.” A vertex with degree zero must still receive an empty adjacency bucket and its own component.

Coloring states in traversals

DFS/BFS implementations often mark vertices unvisited / visiting / visited (three colors) to detect cycles in directed graphs or to avoid revisiting nodes in undirected graphs while still allowing back-edges in theory lectures.

Algorithm	Structure	Typical cost
BFS	Queue	O(V + E)
DFS (adjacency list)	Stack or recursion	O(V + E)
Dijkstra (non-negative)	Priority queue	O((V+E) log V)
Bellman–Ford	Edge relaxation rounds	O(V·E)

Pattern recognition

Minimum moves / transformations

Implicit unweighted graph → BFS over states; store predecessors if the path is required.

Dependencies / prerequisites

Directed graph → topological sort or three-color DFS; cycle means no valid order.

Groups / provinces / islands

Connected components → traversal or DSU; include every isolated item.

Accounts / identifiers / equality

Dynamic connectivity → DSU, often after mapping strings to compact integer IDs.

Cheapest route

Weighted shortest path → inspect weight constraints before choosing BFS, Dijkstra, Bellman–Ford, or DAG DP.

Critical links / failure points

DFS low-link values → bridges, articulation points, or SCC condensation.

Proof template: define the state invariant, show initialization, prove each edge scan preserves it, then argue termination and the returned certificate. A traversal order alone is not a correctness proof.

Production graph engineering

Identity and validation

Map external IDs to dense integers when memory matters. Define policies for unknown endpoints, duplicate edges, self-loops, negative weights, overflow, and deterministic neighbor order at the ingestion boundary.

Scale and mutability

Object-heavy adjacency lists are convenient but expensive. Static sparse workloads benefit from CSR; frequently changing graphs need mutation-friendly sets/maps, versioning, or snapshots for concurrent readers.

Representation rule of thumb

For sparse graphs (few edges), use an adjacency list to save space. For dense graphs (many edges), an adjacency matrix can win on O(1) edge lookups. At massive scale, graphs are often sharded; the same invariants still apply per partition and at the cut.

Exercises

A directed follow graph is weakly connected but not strongly connected. Can every user reach every other user? What algorithm distinguishes the two notions?
V = 10⁵, E = 2×10⁵. Compare memory for an adjacency list vs a boolean V×V matrix. When would you still choose a matrix?
Counterexample: treating a grid shortest-path task as “weighted Dijkstra” when every move costs 1. What simpler algorithm suffices, and what does it guarantee?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): elementary graph algorithms; representations.
Bondy & Murty, or Diestel, Graph Theory: walks, trails, paths, and connectivity definitions.
Ahuja, Magnanti, Orlin: network flows (capacity, residual graphs, max-flow min-cut).

Takeaway

Graphs are edge contracts plus vertices. Name direction, weights, and the objective before picking BFS, DFS, Dijkstra, DSU, or flow.