FOUNDATIONS

🕸 What is a Graph?

Take a sheet of paper. Draw some dots. Draw some lines connecting the dots. Congratulations — you just made a graph.

A graph is a collection of nodes (the dots — also called vertices) and edges (the lines — the connections between dots). That's the entire definition. Two ingredients. Nothing else.

But this incredibly simple idea turns out to be one of the most powerful tools in all of computer science. Why? Because connections are everywhere.

ABCDEF

Why Graphs Matter

Almost every interesting real-world system is a network of connected things. Graphs give us a universal language to describe, store, and analyze these networks:

🗺️
Road Networks
Every intersection is a node. Every road is an edge. Google Maps uses graph algorithms (Dijkstra's, A*) to find the fastest route between two locations — this happens billions of times per day.
👥
Social Networks
On Instagram, every user is a node. Every follow is a directed edge (I follow you, but you may not follow me). 'People you may know' uses graph algorithms to find users who are 2-3 connections away from you.
🌐
The Internet
Every web page is a node. Every hyperlink is a directed edge. Google's original PageRank algorithm — the one that made Google a trillion-dollar company — is a graph algorithm that ranks pages by how many other pages link to them.
📦
Package Managers
When you run 'npm install', each package is a node and each dependency is an edge. npm builds a dependency graph and uses topological sort to install packages in the right order — dependencies first.
🧬
Biology
Proteins are nodes, interactions are edges (protein interaction networks). Neurons are nodes, synapses are edges (neural networks). Species are nodes, predator-prey relationships are edges (food webs).
✈️
Airlines
Every airport is a node. Every flight route is a weighted edge (weight = distance or cost). Airlines use graph algorithms to find optimal routing, minimize fuel, and handle scheduling.
Every time you use Google Maps, search Google, scroll Instagram, install a package, or book a flight — graph algorithms are running behind the scenes.

What Data Structures and Algorithms are Based on Graphs?

Graphs are the parent structure that many other concepts are built on:

🌲
Trees
A tree is just a graph with no cycles and a single root. Binary trees, BSTs, heaps, tries — all special cases of graphs.
⛓
Linked Lists
A linked list is a graph where each node has exactly one outgoing edge (to the next node). It's the simplest possible graph.
🔍
BFS / DFS
The two fundamental traversal algorithms. BFS uses a queue for level-by-level. DFS uses a stack for deep-first.
🗺️
Dijkstra's / A*
Shortest path algorithms for weighted graphs. GPS navigation, network routing, game pathfinding.
📐
Topological Sort
Ordering nodes by dependencies. Build systems, package managers, course prerequisites.
🤝
Union-Find
Tracking connected groups. Social network clusters, Kruskal's MST algorithm.
🌉
MST (Prim's / Kruskal's)
Connecting all nodes at minimum cost. Network design, clustering.
💪
SCC (Tarjan's / Kosaraju's)
Finding strongly connected components in directed graphs. Web analysis, circuit verification.