Graphs
Cities and roads, friends and followers: what a graph is, two ways to store one, and searching it level by level like ripples or deep first like a maze.
Updated
Graphs
- Who Knows Whom? When Anything Can Connect: Graphs (Journeyman): Find a person's friends in one step, in a network where anyone can know anyone and friendships loop back around: why a list of pairs and a tree both fall short, and the structure that fits, the graph, with one-way and two-way connections and weights.
- Are These Two Friends? Adjacency Lists and Grids (Journeyman): Answer "are these two already friends?" in one step without running out of memory, before every Add friend button: why reading a friend list and a box for every pair both fall short at a million people, and how to choose between an adjacency list, a set per person and an adjacency matrix.
Searching a Graph
- How Many Steps Apart? Breadth-First Search (Journeyman): Find how many friendships apart two people are, the fewest, without listing every route or walking in circles: why both of those fail, and the search that fixes them, breadth-first search, with a queue and a visited set.
- Who Can I Reach? Depth-First Search (Journeyman): Find everyone a person can reach through friends, and split a network into the groups that don't touch, with a short recursive walk that never goes round in circles: why the folder walk from Module 3 loops forever here, and the search that fixes it, depth-first search, and when to choose it over breadth-first search.
Exercise: Friends of Friends
- Exercise: Friends of Friends (Journeyman): A small social app needs a "people you may know" box and a "how many steps apart?" line that stay fast in a town of 90,000 people: turn the app's list of friendships into something quick to search, write both features, and let the tests check them, the big town included.