在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连（当然从 j 到 i 也一定有路径），则称 i 和 j 是连通的。如果图中任意两点都是连通的，那么图被称作连通图。

极大连通子图要根据例子理解：

case 1： 该图本身就是一个连通图，则极大连通子图就是它自己。 case 2： 该图本身不是一个连通图，则极大连通子图是每一个连通的图，每一个单独的连通图称之为一个连通分量，就是说非连通图的极大连通子图叫做连通分量。下图有两个极大连通子图、两个连通分量。

一个连通图的极小连通子图就是该连通图的生成树。生成树保证了：

也就是我们对原连通图的边进行最大化删除，却仍保持全图连通的性质得到的图就是一个极小连通子图、一颗生成树。

需要注意的是，生成图是不唯一的，但如果我们对图中的每条边赋予权值，每个边代表着“一定的代价”，所以我们就有了所谓的最小（代价）生成树的概念。