详解伯克算法，让最小有向生成树求解更清晰易懂
A gentle tutorial on Bock's algorithm for minimum directed spanning trees with a structured reformulation
- 用结构化重构替代原算法的隐晦状态更新
- 完整追踪十节点实例，验证算法正确性
- 适合图优化与算法教学研究者阅读
伯克1971年提出的算法是求解最小代价有向生成树问题的精确原始-对偶方法，但其阿尔戈尔语言实现掩盖了数组维护与标签控制流之间的交互。本文提供自包含教程，包括原始代码、逐行解释、三节点电路构造示例，以及伯克十节点实例的完整执行追踪。此外，提出一种结构化重构：将临时的边标签变更替换为显式的连通分量与路径状态。局部紧致性与收缩进展结果，结合操作对应定理，证明该重构保持了原算法的所有候选选择、转移路径与最终解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。