0
Challenge · 51Graphs
Graphs and adjacency lists
Graphsused in ~95% of apps
A tree with the rules removed. No node on top, loops allowed, and it may come in several pieces. Almost everything you have built in the last two tiers works here with one line added.
Core idea. A graph is nodes joined by edges, with none of a tree's guarantees. You almost always store it as an adjacency list, meaning one row per node holding its neighbours, because that is the only thing any algorithm ever asks for. The one line every graph algorithm adds is a seen set, because without it a loop makes you walk forever.
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
click a node to see its row of the list
adjacency list
0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]
4: [5]
5: [4]
A graph is nodes joined by edges. Unlike a tree it may have loops, and it may come in separate pieces.
Nodes 4 and 5 are joined to each other and to nothing else. A graph does not have to be one piece.
↑ play a little first, then dig in