Intermediate · 20 minYou are hereRead
Graphs and how to store them
A graph is vertices joined by edges, stored as a V × V adjacency matrix of yes-or-no cells or as a list of neighbours for each vertex.
Graphs
Graphs
Members: · Free account
Lessons on this topic
Intermediate · 20 minYou are hereRead
Breadth-first search
Exploring from a start vertex with a queue reaches vertices in order of their distance in edges, and the parents lead back along a shortest route.
Intermediate · 20 minYou are hereRead
Depth-first search
Going as far as possible along each branch before backing up visits every reachable vertex, with the call stack remembering the way back.
Intermediate · 18 minYou are hereRead
Topological order
In a graph of tasks with no cycle, every task can be listed after the tasks it depends on, by Kahn’s method or by reversing a depth-first search’s finishing order.
Intermediate · 22 minYou are hereRead
Dijkstra's algorithm
With no negative road lengths, settling the nearest unsettled town again and again, and relaxing its roads, gives every shortest distance from the start.
Intermediate · 18 minYou are hereRead
Prim's algorithm
Growing a tree from one town by always adding the cheapest road that leaves it connects every town at the least total cost.
Intermediate · 16 minYou are hereRead
Union–find
An array of parent indices keeps items in groups as trees; joining links one root under another, and finding flattens the path it climbs.
Intermediate · 16 minYou are hereRead
Kruskal's algorithm
Taking roads from cheapest to dearest, and keeping each one that joins two separate groups, builds the same least-cost network as Prim’s algorithm.
Related topics