Graph Theory: Maps of Meaning

1. Introduction: Connecting the Dots

A Graph is simply a set of objects (Nodes) connected by links (Edges). It is the universal language of relationships.

  • Social Networks: Nodes = People, Edges = Friendships.
  • The Internet: Nodes = Servers, Edges = Cables.
  • Google Maps: Nodes = Intersections, Edges = Roads.
  • Knowledge Graphs: Nodes = Concepts, Edges = Relationships (e.g., “Paris” → “is capital of” → “France”).

Key Terminology

  • Vertex (Node): The entity (V).
  • Edge: The connection (E).
  • Directed vs Undirected:
    • Undirected: Friendship (If A is friends with B, B is friends with A).
    • Directed: Twitter Follow (A follows B ≠ B follows A).
  • Weighted vs Unweighted:
    • Unweighted: Every connection is equal.
    • Weighted: Roads have distances or traffic costs.

2. Representation: Matrix vs List

How do we store a graph in a computer? This is a classic System Design trade-off.

A. Adjacency Matrix

A 2D array M[i][j] where 1 means a connection exists and 0 means it doesn’t.

  A B C
A 0 1 0
B 1 0 1
C 0 1 0
  • Pros:
    • Fast lookup: Check if A is connected to B in O(1).
  • Cons:
    • Space heavy: Uses O(V2) memory.
    • Bad for Sparse Graphs (e.g., Social Networks where you know 500 people out of 8 billion).

B. Adjacency List

An array of lists. Each node stores a list of its neighbors.

  • A: [B]
  • B: [A, C]

  • C: [B]

  • Pros:
    • Space efficient: Uses O(V + E) memory.
    • Perfect for Sparse Graphs.
  • Cons:
    • Slower lookup: Check if A connects to B takes O(Degree of A).

[!TIP] Interview Tip: In almost all real-world applications (Social Networks, Web Crawlers), we use Adjacency Lists because graphs are sparse. $V^2$ is simply too big when $V$ is in the millions.

3. Interactive Visualizer: Pathfinding Race (BFS vs DFS)

How do we explore a graph?

  1. BFS (Breadth-First Search): Explores neighbors layer by layer (like a Wave or Water). Uses a Queue. Guarantees shortest path in unweighted graphs.
  2. DFS (Depth-First Search): Explores as deep as possible before backtracking (like a Maze solver). Uses a Stack.

Instructions:

  1. Draw Walls on the grid by clicking/dragging.
  2. Click Run BFS (Blue) or Run DFS (Green).
  3. Watch how they explore!
Start (S) → Target (T) | Draw Walls with Mouse/Touch
Ready

4. Summary

  • Graphs model relationships.
  • Adjacency List ($O(V+E)$) is preferred for sparse real-world graphs over Adjacency Matrix ($O(V^2)$).
  • BFS (Queue) finds the shortest path in unweighted graphs (Wave).
  • DFS (Stack) explores deep and is used for mazes, topological sorting, and cycle detection.

Next: Fourier Transforms →