计算机工程与应用

作者：胡思敏, 王晓峰, 宋家欢, 锁小娜, 颜冬

单位：1.北方民族大学 计算机科学与工程学院，银川 750021；2.北方民族大学 图形图像智能处理国家民委重点实验室，银川 750021；

关键词：最小割问题,最大流问题,图算法

基金：宁夏自然科学基金（2024AAC03165，2024AAC03169）；宁夏青年拔尖人才项目（2021）。

最小割问题是图论中的经典NP-难问题，广泛应用于数字医学图像视差处理、图像分割等方面。最小割问题在不同模型下展现出多样的复杂性特征，近年来针对其求解的算法研究不断推进，主要包括基于流的算法、基于树结构的算法、基于收缩的算法、分布式与并行环境下的算法以及其他组合优化策略在最小割问题中的应用等。系统梳理了最小割问题的研究现状与算法发展脉络，从算法设计原理、结构适应性、性能对比等方面展开综述。总结各类算法的优势与局限，归纳适用场景与发展趋势，并展望最小割问题在复杂图结构下的研究方向，旨在为相关研究提供理论支持与方法指导。

来源：2026年第3期

《计算机工程与应用》期刊编辑部

查看计算机工程与应用杂志2026年第3期