- 从图上选出一些边，使整个图具有连通性，同时让选中的边的权值总和（以下称为解的“开销”）最小。这类问题称为最小生成树问题。
- 克鲁斯卡尔算法(Kruskal)
- 该算法的基本思路是按权值从小到大的顺序，以“如果把某条边添加到解（新图）中不会产生圈，则向解中添加该边”为规则，一次对各边进行操作，直到新图变成连通图。对于权值相同的边，操作顺序任意。
- 普里姆算法
- 普里姆算法的基本思路是，从只由一个顶点构成的连通分支开始，逐个对顶点进行判断，从而扩张连通分支的规模，直到所有顶点都被连通起来。
- 最小斯坦纳树问题
- 首先给定图G=(V, E),不同的是，这里还要给定一个V的子集U。我们称U中的顶点为终端节点(terminal)。求在包含所有终端节点的G的子树中开销最小的树。
- 和最小生成树问题的不同点在于，在最小生成树问题中，，所有顶点都必须连通起来，而在最小斯坦纳树问题中，我们只要将所有终端节点连通起来即可。换句话说，只要终端节点连通起来，其他节点没有都行。