生成树的概念

问题描述

精选答案

生成树是一张连通图的最小生成树，即含有n个顶点的连通图的生成树必定有n-1条边。

它是由给定的无向图G的所有顶点和边构成的无环连通子图，可以将原图中的所有节点以及连接这些节点的所有边包含进来，但是不能包含环，保持原有的连通性的同时使得生成树中所有边的权值之和最小化。

换而言之，我们可以通过删除无向连通图中的一些边来形成一个生成树，而且可以通过保留该连通图中的所有顶点来实现连通性。

其他回答

学习公社

通俗的说，生成树的概念是：在树状结构中，一个枝叫作一棵树，枝头点分叉两个分枝，叫作生成树。生成树又是一棵树，又可分枝成新的生成树，是嵌套的关系。