0
Challenge · 55Graphs
Topological sort
Graphsused in ~75% of apps
Ordering things when some of them must come before others. Course prerequisites, build steps, task dependencies. And the same algorithm tells you for free whether the requirements are impossible.
Core idea. Repeatedly take anything with nothing left waiting on it, output it, and remove it from the graph. If you get through everything you have a valid order. If you get stuck with items remaining, those items depend on each other in a circle and no order exists.
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
take whatever is waiting on nothing
waiting on
node 0: 0 ready
node 1: 1
node 2: 1
node 3: 2
node 4: 0 ready
node 5: 2
ready queue
04
order so far
[]
count what each node is waiting on. 0 and 4 are waiting on nothing, so they are ready straight away
step 1 of 14
Watch node 3. It drops from 2 to 1 and waits, because a count can say half finished and a tick box cannot.
↑ play a little first, then dig in