Disjoint Sets, and the Cheapest Way to Connect Everything
Twelve lines of code, two operations, and a running time so close to constant that nobody bothers with the difference. Then minimum spanning trees for free.
Problem Solving From Zero15
Subject · 4 posts
graphs
Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall
Three algorithms, three different jobs. Which one to reach for depends on negative edges, on how many sources you have, and on nothing else.
Problem Solving From Zero14
Depth-First Search: Cycles, Components, and Topological Order
BFS goes wide, DFS goes deep, and the difference is not stylistic. DFS answers questions about structure that a queue simply cannot see.
Problem Solving From Zero13
Graphs: How to Store One, and Breadth-First Search
Half of all algorithm problems are graph problems in disguise. Here is how to represent a graph, and the search that finds shortest paths for free.
Problem Solving From Zero12