数据结构什么是最小生成树？有几种方式构造

数据结构什么是最小生成树？有几种方式构造

普里姆算法的基本思想:取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。

之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。

克鲁斯卡尔算法克鲁斯卡尔算法的基本思想：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。

数据结构最小生成树

htt

最小生成树是什么？

1.生成树从前述的深度优先和广度优先遍历算法知，对于一个拥有n个顶点的无向连通图，它的边数一般都大于n－1。生成树是指在连通图中，由n个顶点和不构成回路的n－1条边构成的树。

若由深度优先遍历得到的生成树称为深度优先生成树，则由广度优先遍历得到的生成树称为广度优先生成树。

再进一步分析可知，对于满足条件，连通图的n个顶点和不构成回路的n－1条边构成的生成树有多棵，换言之，图的生成树不唯一。2.最小生成树对于带权的图，其生成树的边也带权，在这些带权的生成树中必有一棵边的权值之和最小的生成树，这棵生成树就是最小（代价）生成树。 最小生成树在实际中具有重要用途，如在通信网的设计中，用顶点表示城市，用边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用，这n个城市之间最多可以建n（n－1）／2条线路。如果要求在任意两个城市之间都有线路相连，且建设费用最少，即从n（n－1）／2条边中选取权值最小的n－1条，这就是最小生成树问题。

2.构造最小生成树的基本原则（1）尽可能选取权值最小的边，但不能构成回路。 （2）选择n－1条边构成最小生成树。 常见的最小生成树算法有普里姆（Prim）算法和克鲁斯卡尔（kruskal）算法两种。

最小生成树是什么

最小生成树其实是最小权重生成树的简称。一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。

【应用问题】许多应用问题都是一个求无向连通图的最小生成树问题。

例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。 【说明】最小生成树性质：设G=(V，E）是一个连通网络，U是顶点集V的一个非空真子集。若(u，v）是G中一条“一个端点在U中（例如：u∈U），另一个端点不在U中的边（例如：v∈V-U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包括此边（u，v）。

【举例】网络G表示n个城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价）。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。

数据结构最小生成树问题

#in