A lesson from the Data Structures module of the bootcamp. About a 12 minute read.
A graph is nodes joined by edges, and it is the most general structure there is. Everything else in this module is a graph with a restriction added. A linked list is a graph where every node has one neighbor. A tree is a graph with no cycles and a chosen root. A grid is a graph whose edges come from coordinates. Learn trees first, then lift the restriction.
A graph is a set of VERTICES joined by EDGES. Edges can be directed (a one-way link, like a dependency) or undirected (a two-way link, like a friendship), and they can carry a WEIGHT (a cost, a distance or a capacity). Two words decide which algorithm you need: 'cycle' and 'weight'. No cycles and one root: it is a tree, and recursion works with no bookkeeping. Cycles but no weights: BFS gives you shortest paths. Weights: you need Dijkstra's algorithm, or Bellman-Ford if any weight is negative. Getting those four cases straight in your head is most of what graph fluency is.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 576 practice puzzles