Graph Theory: Maps of Meaning

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

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 (Distance = 1).
  • Weighted: Roads have distances or traffic costs (Distance = 5).

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.

  A B C
A 0 1 0
B 1 0 1
C 0 1 0
  • Pros: Fast lookup (O(1)).
  • Cons: Space heavy (O(V2)). Bad for Sparse Graphs.

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 (O(V + E)).
  • Cons: Slower lookup (O(Degree)).

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

3. Interactive Visualizer: Pathfinding Arena

How do we explore a graph?

  1. BFS (Breadth-First Search): Explores layer by layer (Wave). Shortest path for Unweighted graphs.
  2. DFS (Depth-First Search): Explores deep (Maze). Good for puzzles.
  3. Dijkstra: Explores by “Cheapest Cost” first. Shortest path for Weighted graphs.

Instructions:

  1. Draw Walls (Gray) to block paths.
  2. Add Mud (Brown) to increase cost (Cost = 5).
  3. Compare BFS (ignores Mud cost) vs Dijkstra (avoids Mud).

[!TIP] Try it yourself: Select Mud and draw a line across the path. Run BFS (it will go straight through, high cost) and then Dijkstra (it will go around or find the thinnest part).

Ready

4. Dijkstra’s Algorithm: Handling Weights

BFS works perfectly when every edge has a distance of 1. But what if one road is a highway (1 min) and another is a dirt road (10 mins)?

Dijkstra’s Algorithm is a “Greedy” algorithm. Instead of a simple Queue, it uses a Priority Queue (typically a Binary Heap). It always expands the “Cheapest Known Node” next.

  1. Assign distance to Start = 0, all others = ∞.
  2. Add Start to Priority Queue.
  3. While Queue is not empty:
    • Pop node with smallest distance (Min-Heap: O(log V)).
    • Check neighbors. If Dist(Current) + Weight < Dist(Neighbor), update Neighbor and add to Queue.

Complexity: O(E log V). This guarantees the shortest path even with weights (assuming no negative weights).

5. Topological Sort: Resolving Dependencies

Imagine you are compiling code.

  • lib_A depends on lib_B.
  • lib_B depends on lib_C.

You must compile C, then B, then A. This ordering is a Topological Sort. It only works on DAGs (Directed Acyclic Graphs). If there is a cycle (A → B → A), you have a deadlock/infinite loop.

Interactive Dependency Resolver: Click “Next Step” to simulate Kahn’s Algorithm.

  1. Find nodes with In-Degree = 0 (No prerequisites).
  2. “Compile” them.
  3. Remove their outgoing edges.
  4. Repeat.
Processing Queue (In-Degree 0)
[]
Compiled Order
[]

6. Summary

  • Graphs: The skeleton of the internet and social networks.
  • BFS: Wave expansion. Shortest path on unweighted graphs.
  • Dijkstra: Cheapest expansion (O(E log V)). Shortest path on weighted graphs.
  • Topological Sort: The order of operations for dependencies (Kahn’s Algorithm).