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.

---

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(V²)
• Lookup: O(1)
• Best for: Dense graphs (many edges).

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).

---

6. Implementation: Adjacency List (Java & Go)

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);
  }
}

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 ∈ 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!).