对一个具有 $n$ 个点的连通图进行遍历，对于遍历后的子图，若其包含原图中所有的点且保持图连通，那么这个连通图是在边最少的情况下保持图连通的子图，即极小连通子图，其结构一定是一个具有 $n-1$ 条边的树，通常称为生成树
对于生成树来说，若除去其一条边，则会变为非连通图，若添加一条边，则会形成图中的一条回路
在生成树问题中，最常见的问题就是最小生成树问题，所谓最小生成树，就是对于一个有 $n$ 个点的无向连通图的生成树，其包含原图中的所有点，且保持图连通的边权总和最少的边
简单来说，对于一个有 $n$ 个点的图，边一定是大于等于 $n-1$ 条的，最小生成树，就是在这些边中选择 $n-1$ 条出来连接所有的 $n$ 个点，且这 $n-1$ 条边的边权之和是所有方案中最小的
最小生成树具有以下两条性质：
- 切割性质：连接点 $x$、$y$ 的边权最小的边必定被生成树包含
- 回路性质：任意回路/环上的边权最大的边必不被生成树包含
解决最小生成树问题的算法有：
