最大流问题与 Edmonds-Karp 算法
从贪心找路失败出发,引出反向边的纠错机制,形式化残量网络与增广路,用 BFS 实现标号法并反复推流,直到残量网络中源汇不再连通。
0-1 背包问题(动态规划、回溯法、分支限界法)
从决策树到分支限界,三种视角求解 0-1 背包:动态规划求最优值,回溯法与分支限界用上界剪枝。
Dijkstra 单源最短路径
每次从未敲定顶点中选出距源点最近者,松弛它的所有出边,逐步得到源点到各顶点的最短距离。
Kruskal 最小生成树
把边按权值升序排序,从小到大扫描;只要加入后不成环就保留,最终让森林合并成最小生成树。
Prim 最小生成树
从任意起点出发,每一步选择权值最小的跨切边,把树外顶点并入树内,逐步构造最小生成树。
贪心算法:哈夫曼编码
用贪心思想构造哈夫曼树:每次合并频率最小的两个节点,得到平均码长最短的前缀码,实现数据压缩。
最短等待时间(加工顺序问题)
用贪心思想解决加工顺序问题:让耗时短的任务先执行,从而最小化所有任务的总等待时间。
旅行售货员问题(回溯法与分支限界法)
从排列树回溯到矩阵归约下界剪枝,深入解析旅行售货员问题的精确解法,理解 NP-Hard 问题的搜索与剪枝思想。