计算图的支配者：从 1959 到 Lengauer-Tarjan 的算法漫游

📋 概述

作者因一个新玩具项目需要支配树，深入钻研了图支配者的计算算法。文章先给出支配与立即支配的直观定义，再梳理 1959 年以来连绵的研究：Lengauer-Tarjan 是 LLVM 采用的标准算法但实现复杂，2001 年的「简单快速支配算法」宣称既好学又在实践中比 LT 快 2.5 倍，而更严谨的对比研究则给出了相反结论，体现这类算法「实现细节决定成败」的特性。