Algorithm dossier

  • Category: MST
  • Worst-case complexity: O(n²)
  • Approach: Greedy
  • Data structure: Graph
  • First formalised: 1950s

Why this snippet is Prim's Algorithm

Why Prim. Builds a minimum spanning tree by repeatedly attaching the cheapest *outgoing* edge from the current tree. f[v] tracks the minimum-weight edge connecting v to the partial tree; the inner relaxation f[v] = g[u][v] is *direct edge weight*, not cumulative path cost. vs. Dijkstra. Dijkstra's relaxation is f[u] + c (path cost); Prim's is just c (edge cost). Same outer skeleton, different inner recipe.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.