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.
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