展开全部
生成树是一个包含n个结点的连通图G的一个子图。该子图必须包含G中的所有n个结点以及G中的n-1条边并且保持连通性。
最小生成树是G的所有可能的生成树中,n-1条边的权值总和最小的那一个(或多个)生成树。
最小生成树是G的所有可能的生成树中,n-1条边的权值总和最小的那一个(或多个)生成树。
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
一些定义:
1.一个连通且无回路的无向图称为树.
2.若图G的生成子图是一棵树,则该树称为G的生成树.
3.在图G的所有生成树中,树权最小的那棵生成树,称作最小生成树.
关于找出最小生成树的两种算法,一个称为Kruskal(克鲁斯卡尔),另一个叫Prim(普里姆)。从二者的原理来看,Kruskal是基于边的算法,Prim是基于顶点的.因此对于一个边数很多的图,用Kruskal算法不明智.而顶点多边少的图用Kruskal效率多了。
1.一个连通且无回路的无向图称为树.
2.若图G的生成子图是一棵树,则该树称为G的生成树.
3.在图G的所有生成树中,树权最小的那棵生成树,称作最小生成树.
关于找出最小生成树的两种算法,一个称为Kruskal(克鲁斯卡尔),另一个叫Prim(普里姆)。从二者的原理来看,Kruskal是基于边的算法,Prim是基于顶点的.因此对于一个边数很多的图,用Kruskal算法不明智.而顶点多边少的图用Kruskal效率多了。
参考资料: http://baike.baidu.com/view/288214.htm
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
连接所有点,而且所有边的权值之和最小
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询