nnpc.net
当前位置:首页 >> 数据结构里,最小生成树,是不是只能是带权无向图... >>

数据结构里,最小生成树,是不是只能是带权无向图...

无向有向都能做.不带权更简单,所有边的权值都设为1即可.

肯定不是.考虑极端例子:N个点的完全连通无向图,边权都是1,那么它的不同的最小生成树 就是巨多无比了.

对,最小的意思就是权值和最小

一些定义:1.一个连通且无回路的无向图称为树.2.若图G的生成子图是一棵树,则该树称为G的生成树.3.在图G的所有生成树中,树权最小的那棵生成树,称作最小生成树.关于找出最小生成树的两种算法,一个称为Kruskal(克鲁斯卡尔),另一个叫Prim(普里姆).从二者的原理来看,Kruskal是基于边的算法,Prim是基于顶点的.因此对于一个边数很多的图,用Kruskal算法不明智.而顶点多边少的图用Kruskal效率多了.

先找出最小生成树,然后把各边权相加.2+4+5+7=18

一个图中,最小生成树一定是从某个节点出发得到的最短路径树,从某个结点出发,是求最小生成树的是普里姆算法吧,要克鲁斯卡尔算法,就不需要指定从某个结点出发,也就是算法策略不同,操作的步骤就不一样的

C 最小生成树,这也是最小生成树的一个性质,构造最小生成树的方法都需要以此为基准!

需要,你的结果是2棵树(森林),结果要的是一棵树,当然要连起来

网站首页 | 网站地图
All rights reserved Powered by www.nnpc.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com