最小生成树

• 克鲁斯克尔 Kruskal 算法
  • 基本思想：按权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路
  • 具体做法：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

最短路径

• 迪科斯彻 Dijkstra 算法
  • 基本思想：逐渐递归地求出从起点到各个节点的最短路径，直到计算出从起点到终点的最短路径

网络与最大流量

• Ford-Fulkerson 算法
  • 基本思想：只要有一条从源点（开始节点）到汇点（结束节点）的路径，在路径的所有边上都有可用容量，就沿着这条路径发送一个流，流量由路径上的最小容量限制。 然后再找到另一条路径，一直到网络中不存在这种路径为止。 一条有可用容量的路径被称为一条增广路径
  • 具体做法：不断寻找可用路径，累加可用路径的短板流量后，删除该路径上的短板流量，以此循环直到找不到任何何可用路径

线性规划

• 在一组约束条件下寻找目标函数的极值问题
• 快速解：两两联立方程求解顶点值