A lesson from the data structures and algorithms 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 bolted on: a linked list is a graph where every node has one neighbour, a tree is a graph with no cycles and a chosen root, a grid is a graph whose edges are implied by coordinates. Learn trees first, then remove the restriction.
A graph is a set of VERTICES joined by EDGES. Edges may be directed (a one-way link, like a dependency) or undirected (a two-way link, like a friendship), and they may carry a WEIGHT (a cost, distance, or capacity). The two words that decide which algorithm you need are '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, 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 536 practice puzzles