A gentle tutorial on Bock's algorithm for minimum directed spanning trees with a structured reformulation

A line-by-line guide to Bock’s 1971 minimum-cost arborescence algorithm, with worked traces and a readable reformulation proved to make the same choices

arXiv 2026

Yuxi Wang1, Jungyeul Park2

1UBC, Canada 2KAIST, South Korea

Paper (arXiv) PDF Code

Abstract

Bock's 1971 algorithm is an exact primal–dual method for the minimum-cost arborescence problem, but its Algol presentation obscures the interaction of its maintained arrays and label-directed control flow. We provide a self-contained tutorial comprising the original listing, a line-mapped explanation, a circuit-forming three-node example, and a complete trace of Bock's ten-node instance. We also present a structured reformulation that replaces temporary span-label changes with explicit component and trace state. Local tightness and contraction-progress results, together with an operational-correspondence theorem, establish that the reformulation preserves Bock's candidate choices, transfers, and final solution.

Keywords Bock's algorithm Minimum directed spanning tree Minimum-cost arborescence Optimum branching Primal-dual method Chu-Liu/Edmonds Algol 60 listing Tutorial Algorithm trace

What the Tutorial Covers

Given a directed graph with a designated origin and a cost C[I, J] for each link I → J (rows = initial nodes, columns = terminal nodes), the task is to find a rooted spanning arborescence of minimum total cost. Bock's procedure solves it without building reduced graphs: it keeps the original cost matrix and node indices, records provisional links as stars, represents contracted circuits by common SPAN labels, and uses bars to drive later exchanges. The tutorial is organized as follows:

  1. The original Algol listing (statement labels L1–L100), reproduced verbatim, with the matrix conventions and maintained state defined.
  2. A line-mapped explanation that preserves Bock's variables, tests, assignment order, and control flow: candidate search (L4), column adjustment (L5), backward trace and circuit test (L6–L8), and the star-and-bar transfer (L9–L11).
  3. A three-node example that isolates circuit formation, contraction, and the ensuing transfer.
  4. A complete trace of Bock's original 10 × 10 instance, covering every candidate search, column adjustment, backward trace, contraction, and transfer from initialization to the reported optimum (the source paper gives only a partial computation).
  5. A structured reformulation (implemented as bock_algorithm_readable) with separate candidate-selection, column-adjustment, backward-trace, contraction, and transfer phases. It replaces negative SPAN labels by an explicit trace mask and fresh contraction labels by the active component's label. Lemma 1 (candidate tightness), Lemma 2 (progress under contraction), and Theorem 1 (operational correspondence) show that, under the same scan order and tie-breaking convention, it selects the same candidates, applies the same adjustments and transfers, and returns the same arborescence and objective value.
Principal arrays maintained by Bock's procedure (Table 1 in the paper), with their names in the readable implementation (Table 2 in the paper).
BockReadable implementationRole
U1[J]U1[J]Amount subtracted from the costs of links entering J; the reduced cost of I → J is C[I, J] − U1[J].
I*[J]parents[J]Initial node of the link currently starred into J (0 = no starred link).
(Ī[J], J̄[J])candidate_edges[J]Candidate link whose backward trace passed through J; identifies the next candidate when a transfer displaces J's star.
SPAN[J]components[J]Label of the span (contracted component) containing J.
Negative SPAN labelscycle_traceSpans visited by the current backward trace.

Worked Examples

  • Three-node example. Origin 1 and links 1→2 (cost 50), 1→3 (60), 2→3 (10), 3→2 (20). The two cheapest entering links, 3→2 and 2→3, form a circuit; after contraction and transfer the procedure returns T* = {1→2, 2→3} with Z = 50 + 10 = 60, the unique minimum (final state U1 = (0, 50, 40), I* = (0, 1, 2), SPAN = (1, 4, 4)).
  • Bock's ten-node instance (origin node 10, no infeasible arcs). The complete trace contains two circuits resolved at K = 4 and K = 5, contractions at K = 7, and two contractions with three L4 passes at K = 9. It terminates with the arcs 6→1, 4→2, 2→3, 1→4, 4→5, 10→6, 6→7, 9→8, 4→9 and Z = 22 + 3 + 2 + 7 + 0 + 26 + 5 + 6 + 16 = 87, matching Bock's reported optimum.
  • Reformulation. The structured procedure is proved to make the same candidate choices and transfers and to return the same final solution as the Algol listing; both are implemented in the accompanying Python repository.
Three-node example: all feasible arborescences rooted at node 1 and their costs (Section 3.5 in the paper). Bock's procedure returns the first.
ArborescenceCost
{1→2, 2→3} (returned)50 + 10 = 60
{1→3, 3→2}60 + 20 = 80
{1→2, 1→3}50 + 60 = 110

BibTeX

@misc{wang2026gentletutorialbocksalgorithm,
      title={A gentle tutorial on Bock's algorithm for minimum directed spanning trees with a structured reformulation}, 
      author={Yuxi Wang and Jungyeul Park},
      year={2026},
      eprint={2603.27530},
      archivePrefix={arXiv},
      primaryClass={cs.CL},
      url={https://arxiv.org/abs/2603.27530}, 
}
More projects from KAIST MLP Lab →