Everyone knows everyone

Graphs as Friendship Maps

The analogy

🧸 ELI5⚙ Tech

A friendship map is messier than an org chart: friendship goes both ways, circles loop back on each other, and there is no single person at the top. A graph is just dots (people) joined by lines (relationships). And here is the family secret: the org chart from last lesson IS one of these — a tree is simply a graph that happens to have no loops and one person at the top.

Visualizer

Dots, lines and loops

step 1 / 6

Eight dots, ten lines. No root, no hierarchy — just relationships.V = 8, E = 10

🎯 Predict modespeed1×

📖 In depth — the full reference

🐍 PythonJS JavaScript

The two representations

aspect	adjacency LIST	adjacency MATRIX
memory	O(V + E) — only real friendships stored	O(V²) — every possible pair, mostly zeros
edge lookup u—v?	O(degree(u))	O(1) — matrix[u][v]
list all neighbours of u	O(degree(u)) — already a list	O(V) — scan the whole row
add edge	O(1)	O(1)
best for	sparse graphs (almost all real ones)	dense graphs, or O(1) edge tests

Graph vocabulary you now own

directed vs undirected (one-way vs mutual), weighted (edges carry costs — Module 6 lives here), degree (edge count at a node).
path (walk along edges), cycle (a path back to where you started), connected (everyone reachable from everyone).
A tree is exactly the special case: connected, acyclic, one designated root — every tree is a graph, not every graph is a tree.
Facebook friendships: undirected. Twitter follows: directed. Flight prices: directed AND weighted. Your codebase's imports: directed, and you pray acyclic.

Python: dict of lists

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}
print(len(graph["A"]))          # degree of A — O(1) lookup + O(1) len
print("D" in graph["B"])        # edge test — O(degree)

# weighted variant: dict of dicts
costs = {"A": {"B": 5, "C": 2}}
print(costs["A"]["C"])           # 2 — O(1) edge lookup, list AND matrix perks

PythonJavaScriptHow devs thinkWhere it's used

adj = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
}

len(adj["B"])        # degree of B
"C" in adj["A"]      # is there an edge?
# space O(V + E) — right for sparse graphs

Check yourself

A tree is…

Practice — write it yourself

🐍 PythonJS JavaScript

degree_of(adj, node): adj is {"A": ["B","C"], ...}. Return how many friends (edges) the node has — 0 if the node is unknown.

Python 3 · runs in your browser · your draft is saved locally

📝 My notessaved in this browser