Introduction to Graphs

[!NOTE] This module explores the core principles of Introduction to Graphs, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: Non-Linearity

Until now, we’ve dealt with linear (Linked Lists) or hierarchical (Trees) data. But the real world is a web. Friendships, road networks, and the internet don’t have a “root”—they have connections.

A Graph G = (V, E) is the ultimate abstraction for modeling relationships between entities.

📖 War Story: The Twitter “Justin Bieber” Problem

In the early days of social media, naive graph representations caused massive outages when celebrities with millions of followers tweeted. If the graph of “Followers” was traversed poorly (e.g., iterating through a dense matrix to fan out a tweet to 50 million users), the cache would thrash and the database would lock. Companies had to rethink their graph topology, migrating to Adjacency List-based distributed cache architectures where “high-degree” nodes (celebrities) were handled via a specialized “pull” model rather than a standard “push” fanout. This is why understanding your graph’s density and node degrees is critical to scale!

2. The 4 Pillars of Graph Mastery

Pillar Focus Why it matters
1. Intuition Modeling Relationships Deciding if a problem is BFS (shortest path) or DFS (connectivity).
2. Rigor Lemma Proofs Proving properties like the Handshaking Lemma to bound edge counts.
3. Hardware Matrix vs. List Knowing why large Sparse graphs must use Adjacency Lists for cache efficiency.
4. Optimization Union-Find & Heaps Using specialized structures to make Dijkstra and Kruskal’s efficient.

3. Core Classifications

  1. Direction: Undirected (symmetric connections like Facebook friends) vs. Directed (asymmetric like Twitter followers).
  2. Weight: Unweighted (all hops are equal) vs. Weighted (edges have costs, like Google Maps distances).
  3. Cycles: Cyclic (looping back to start) vs. Acyclic (no loops). A DAG (Directed Acyclic Graph) is vital for build systems.

4. Interactive: Graph Classifier

Click to transform the graph and see how direction and weight change its behavior.

Standard Undirected Graph.

5. Physical Representations: Matrix vs. List

How do we represent this abstract structure in memory?

A. Adjacency Matrix (2D Array)

A V x V grid where matrix[i][j] is 1 if an edge exists.

  • Space: O(V2)
  • Lookup: O(1)
  • Best for: Dense graphs (many edges).
  • Hardware Reality: Since it’s a contiguous 2D array, iterating over neighbors of a vertex benefits from CPU cache spatial locality, making it extremely fast for dense operations. However, for a graph with 1 million users and 100 edges each, an Adjacency Matrix would require 1 Trillion cells (1TB of memory), mostly filled with 0s. This is a massive waste of RAM.

B. Adjacency List (Array of Lists)

An array of size V, where each entry is a list of neighbors.

  • Space: O(V + E)
  • Lookup: O(Degree)
  • Best for: Sparse graphs (most real-world graphs).
  • Hardware Reality: Adjacency lists save massive amounts of memory for sparse graphs. But because the lists of neighbors are often dynamically allocated (e.g., ArrayList in Java, pointers in a linked list), traversing them can cause cache misses due to memory fragmentation. In high-performance systems, Adjacency Lists are often flattened into a single contiguous array (CSR - Compressed Sparse Row format) to get the best of both worlds: memory efficiency and cache locality.

6. Implementation: Adjacency List (Java & Go)

Java

class Graph {
  private Map<Integer, List<Integer>> adj = new HashMap<>();

  public void addEdge(int u, int v) {
    adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
    adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
  }
}

Go

type Graph struct {
  Adj map[int][]int
}

func (g *Graph) AddEdge(u, v int) {
  g.Adj[u] = append(g.Adj[u], v)
  g.Adj[v] = append(g.Adj[v], u)
}

7. Deep Dive Strategy Lab: Graph Basics

Intuition Through Analogy

Think of this like city route planning. An Adjacency Matrix is a massive grid map of every single intersection (Too much detail for a small town). An Adjacency List is a list of highway signs for each exit (Only tells you where you can go).

Mathematical Anchor: The Handshaking Lemma

In any undirected graph, the sum of the degrees of all vertices is exactly twice the number of edges.

Σv &in; V deg(v) = 2 E

The Proof

Every edge e = (u, v) contributes exactly +1 to the degree of u and +1 to the degree of v. Since every edge has exactly two endpoints, the total count of “end-points” (sum of degrees) must be 2 × the number of edges.

[!TIP] Corollary: In any graph, the number of vertices with an odd degree must be even. (Try to draw a graph that breaks this—you can’t!).