0
Challenge · 53Graphs
DFS and connected components
Graphsused in ~95% of apps
Your first real graph algorithm, and it is code you already have. A depth first walk plus a seen set answers a whole family of questions about how a graph is joined together.
Core idea. Depth first search follows one path as far as it goes, then backs up and tries the next. On a graph the only addition is a seen set. Running it from every unvisited node in turn tells you how many separate pieces the graph has, and one extra check tells you whether any of them contains a cycle.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
depth first, driven by a stack
the stack, newest on the right
0
put the start on the stack and mark it seen
step 1 of 9
A stack takes the newest first, so it dives down one branch before trying anything else.
↑ play a little first, then dig in