11.4 生成树

设G是简单图。G的生成树是包含G的每个顶点的G的子图。

比如对于下面的左图，右图就是其生成树中的一种：

所以也可以说：

简单图是连通的，当且仅当它有生成树。

这个概念可以类比到哈赛图，或者关系中的传递性质。

深度优先搜索 / 回溯：DFS

之前还有一个广度优先搜索的内容，用来找最短路径的。

这里深度优先搜索则是在一个简单图中构建生成树的方法。

比如上面这张图，假设以f作为根节点，然后开始构建。

首先就是顺着边走，走过的点不能重复走。

就可以得到下面的图片：

然后从树叶的父母开始，将其作为根节点，重复上面的步骤：

然后继续重复上面的步骤，就可以完成该简单图的生成树了。