32、给定带权无向图，如果图中各边权值互不相同，用普里姆和克鲁斯卡尔算法得到的最小代价生成树一定相同
32、给定带权无向图，如果图中各边权值互不相同，用普里姆和克鲁斯卡尔算法得到的最小代价生成树一定相同
参考答案和解析
正确
相关考题：
B.Kruskal算法：(贪心)按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。function find(v:integer):integer; {返回顶点v所在的集合}var i:integer;
●试题四阅读下列算法说明和算法，将应填入(n)的字句写在答题纸的对应栏内。【说明】下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。图5算法流程图【算法】/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个"有序表"。以顺序表MSTree返回生成树上各条边。*/typedef struct{VertexType vex1；VertexType vex2；VRType weight；}EdgeType；typedef ElemType EdgeType；typedef struct{//有向网的定义VertexType vexs[MAX_VERTEX_NUM]；//顶点信息EdgeType edge[MAX_EDGE_NUM]；//边的信息int vexnum，arcnum；//图中顶点的数目和边的数目}ELGraph；void MiniSpanTree_Kruskal(ELGraph G，SqList MSTree){//G.edge 中依权值从小到大存放有向网中各边//生成树的边存放在顺序表MSTree中MFSetF；InitSet(F，G.vexnum)；//将森林F初始化为n棵树的集合InitList(MSTree，G.vexnum)；//初始化生成树为空树i=0；k=1；while(k (1) ){e=G.edge[i]；//取第i条权值最小的边/*函数fix_mfset返回边的顶点所在树的树根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。*/rl=fix_mfset(F，LocateVex(e.vex1))；r2= (2) //返回两个顶点所在树的树根if(r1 (3) r2){//选定生成树上第k条边if(ListInsert(MSTree，k，e){ (4) ；//插入生成树mix_mfset(E，rl，r2)；//将两棵树归并为一棵树}(5) ；//继续考察下一条权值最小边}DestroySet(F)；}
下面有关图的相关概念说法不正确的是【】A．有e条边的无向图，在邻接表中有e个结点B．有向图的邻接矩阵是对称的C．任何无向图都存在生成树D．不同的求最小生成树的方法最后得到的生成树的权值之和是相等的
对于含有n个顶点的带权连通图，它的最小生成树是指()。A.图中任意一个由n-l条权值最小的边构成的子图B.图中任意一个由n-1条权值之和最小的边构成的子图C.图中任意一个由n-1条权值之和最小的边构成的连通子图D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图
填空题若连通网络上各边的权值均不相同，则该图的最小生成树有（）棵。