Level 4 · Advanced
Free Graphs lessons
12 lessons, about 151 minutes in all. Each teaches one idea with a visual, then gives you one problem built for it. Read the lessons here, then create a free account to solve the problems and keep your progress.
Stage 0Edges and neighbours
- Who is next to whomTurn a list of edges into a list of neighbours for every node.10 min
- Count the connectionsEvery edge adds one to the degree of both of its ends.7 min
- Mutual friendsPut neighbours in sets, then count the people who appear in both.9 min
- Everyone follows themWith one-way edges, count arrows in and arrows out separately.10 min
Stage 1Depth-first
- Go as far as you can, then back upExplore a graph like a maze, marking the places you've been so you never go round in circles.14 min
- Remember the way you cameKeep the trail you are on as a list, adding a node as you enter it and removing it when you back out.15 min
- Remember what each place leads toWhen many routes pass through the same place, count its routes once and reuse the answer.15 min
- Explore with a pile instead of recursionReplace the function calls with your own pile of places to visit, and total up whole connected groups.14 min
Stage 2Breadth-first
- Spread out like a rippleFind the fewest roads between two places by exploring everything one hop away, then two hops, then three.15 min
- One search, every distanceRun the ripple search once and read off how far every place is from the start.14 min
- Stop after k ringsCount who is within a few hops of you by letting the ripple spread only as far as you ask.13 min
- A graph you never drawTreat every state of a puzzle as a place and every move as a road, then use the same ripple search.15 min
There’s more after this
These are the opening stages of Graphs. The full path climbs on to harder problems and a mastery test. Create a free account and we’ll keep your place.
Start the full path free