生成最小生成树的方法

C语⾔实现最⼩⽣成树构造算法最⼩⽣成树最⼩⽣成树（minimum spanning tree）是由n个顶点，n-1条边，将⼀个连通图连接起来，且使权值最⼩的结构。

最⼩⽣成树可以⽤Prim（普⾥姆）算法或kruskal（克鲁斯卡尔）算法求出。

我们将以下⾯的带权连通图为例讲解这两种算法的实现：注：由于测试输⼊数据较多，程序可以采⽤⽂件输⼊Prim（普⾥姆）算法时间复杂度：O（N^2）（N为顶点数）prim算法⼜称“加点法”，⽤于边数较多的带权⽆向连通图⽅法：每次找与之连线权值最⼩的顶点，将该点加⼊最⼩⽣成树集合中注意：相同权值任选其中⼀个即可，但是不允许出现闭合回路的情况。

代码部分通过以下步骤可以得到最⼩⽣成树：1.初始化：lowcost[i]:表⽰以i为终点的边的最⼩权值,当lowcost[i]=0表⽰i点加⼊了MST。

mst[i]:表⽰对应lowcost[i]的起点，当mst[i]=0表⽰起点i加⼊MST。

由于我们规定最开始的顶点是1，所以lowcost[1]=0，MST[1]=0。

即只需要对2~n进⾏初始化即可。

#define MAX 100#define MAXCOST 0x7fffffffint graph[MAX][MAX];void prim(int graph[][MAX], int n){int lowcost[MAX];int mst[MAX];int i, j, min, minid, sum = 0;for (i = 2; i <= n; i++){lowcost[i] = graph[1][i];//lowcost存放顶点1可达点的路径长度mst[i] = 1;//初始化以1位起始点}mst[1] = 0;2.查找最⼩权值及路径更新定义⼀个最⼩权值min和⼀个最⼩顶点ID minid，通过循环查找出min和minid，另外由于规定了某⼀顶点如果被连⼊，则lowcost[i]=0，所以不需要担⼼重复点问题。

xx学院《数据结构与算法》课程设计报告书课程设计题目 PRIM算法求最小生成树院系名称计算机科学与技术系专业（班级）姓名（学号）指导教师完成时间一、问题分析和任务定义在该部分中主要包括两个方面：问题分析和任务定义；1 问题分析本次课程设计是通过PRIM（普里姆）算法，实现通过任意给定网和起点，将该网所对应的所有生成树求解出来。

在实现该本设计功能之前，必须弄清以下三个问题：1．1 关于图、网的一些基本概念1．1．1 图图G由两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。

通常，V（G）和E（G）分别表示图G的顶点集合和边集合。

E（G）也可以为空集。

则图G只有顶点而没有边。

1．1．2 无向图对于一个图G，若边集E（G）为无向边的集合，则称该图为无向图。

1．1．3 子图设有两个图G=（V，E）G’=（V’，）,若V’是V的子集，即V’⊆V ，且E’是E的子集，即E’⊆E，称G’是G的子图。

1．1．4 连通图若图G中任意两个顶点都连通，则称G为连通图。

1．1．5 权和网在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。

把边上带权的图称为网。

如图1所示。

1．2 理解生成树和最小生成树之间的区别和联系1．2．1 生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：V（G’）= V（G）和E（G’）⊆E（G），若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。

1．2．2 最小生成树图的生成树不是唯一的，把具有权最小的生成树称为图G的最小生成树，即生成树中每条边上的权值之和达到最小。

如图1所示。

图1．网转化为最小生成树1．3 理解PRIM（普里姆）算法的基本思想1．3．1 PRIM算法（普里姆算法）的基本思想假设G =（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。

实验5 最小生成树算法的设计与实现一、实验目的1、根据算法设计需要, 掌握连通图的灵活表示方法；2、掌握最小生成树算法，如Prim、Kruskal算法；3、基本掌握贪心算法的一般设计方法；4、进一步掌握集合的表示与操作算法的应用。

二、实验内容1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法；2、设计Kruskal算法实验程序。

有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。

设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。

三、Kruskal算法的原理方法边权排序:1 3 14 6 23 6 41 4 52 3 53 4 52 5 61 2 63 5 65 6 61. 初始化时：属于最小生成树的顶点U={}不属于最小生成树的顶点V={1，2，3，4，5，6}2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6}3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5}4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5}5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5}6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成四、实验程序的功能模块功能模块：bool cmp(Edge a,Edge b)； //定义比较方法x)；//在并查集森林中找到x的祖先int g etfa(intint s ame(int x,int y)； //判断祖先是否是同一个，即是否联通 void merge(int x,int y); //合并子树，即联通两子树sort(e+1,e+m+1,cmp); //对边按边权进行升序排序详细代码：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define M AXN_E 100000#define M AXN_V 100000using namespace std;struct Edge{int f m,to,dist;//边的起始顶点，边的到达顶点，边权}e[MAXN_E];int f a[MAXN_V],n,m; //顶点数组，顶点总数，边总数 //定义比较，只是边权比较bool cmp(Edge a,Edge b){return a.dist < b.dist;}//查找x的祖先是在并查集森林中找到x的祖先x){//getfaint g etfa(intreturn fa[x];if(fa[x]==x)else r eturn fa[x] = getfa(fa[x]);}//判断祖先是否是同一个，即是否联通int s ame(int x,int y){return getfa(x)==getfa(y);}//合并两棵树void merge(int x,int y){int f ax=getfa(x),fay=getfa(y);fa[fax]=fay;}int m ain(){int i;cout<<"请输入顶点数目和边数目："<<endl;cin>>n>>m;//n为点数，m为边数//输出顶点信息cout<<"各个顶点值依次为："<<endl;for(i=0;i<n;i++){fa[i]=i;if(i!=0)cout<<fa[i]<<" ";}cout<<endl;cout<<"请输入边的信息（例子：1 4 5 从顶点1到顶点4的边权为5）"<<endl;for(i=1;i<=m;i++)用边集数组存放边，方便排序和调用 cin>>e[i].fm>>e[i].to>>e[i].dist;//sort(e+1,e+m+1,cmp); //对边按边权进行升序排序表示目前的点共存在于多少个集合中，初始情况是每 int r st=n,ans=0;//rst个点都在不同的集合中for(i=1;i<=m && rst>1;i++){int x=e[i].fm,y=e[i].to;函数是查询两个点是否在同一集合中 if(same(x,y))continue;//sameelse{函数用来将两个点合并到同一集合中 merge(x,y);//mergerst--;//每次将两个不同集合中的点合并，都将使rst值减1这条边是最小生成树中的边，将答案加上边权 ans+=e[i].dist;//}}cout<<ans;return 0;}五、测试数据和相应的最小生成树Input:6 101 2 61 3 11 4 52 3 52 5 63 4 53 5 63 6 44 6 25 6 6Putout:18生成树为：七、思考题1、微软面试题一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。

§3 通讯网络的最小生成树* * 无圈图称为森，连通的无圈图称为树。

若G1是连通图G2的生成子图，且G1本身是树，则称为G1为G2的生成树。

树是最简单但又是十分重要的一类图。

由于其结构简单，它常用来验证图论的某些猜想。

它在许多学科领域中有广泛的应用，例如分子结构，电网络分析等。

最短连接问题与树有关，学科分类和一些决策过程也往往可以用树的形式表示。

树有许多很好的性质：图 T=(V,E)，|V|=n,|E|=m,则下面关于树的命题是等价的。

（1）T是一个树。

（2）T无圈，且m=n-1。

（3）T连通，且m = n-1。

（4）T无圈，但加一新边即得唯一一个圈。

（5）T连通，但舍去一边就不连通。

（6）T中任意两点，有唯一链相连。

上述性质中每一个命题均可作为树的定义，它们对判断和构造树将极为方便。

对图G=（V，E）的每一条边e E赋以相应的实数权 W(e)，得到一个网络，记为N=（V，E，W）。

设T=(V，E’)是N 的一个生成树，令 W（T）= , 则W(T)称为T的权，N 中权最小的生成树称为N的最小生成树。

许多实际问题，如在若干个城市之间建造铁路网、输电网或通信网等，都可归纳为寻求连通赋权图（网络）（eij 的最小生成树问题。

例如已知城市v和v间的直通线路的造价为Wij=w（eij）=（vi,vj）），要求一个总造价为最小的设计方案。

又如一个城市中，对若干新建居民点供应自来水和煤气，已测知连接各点间的直通管道的造价，要求给出一个总造价最小的铺设方案等等。

下面介绍在给定网络N =（V，E，W）内求最小生成树的两种算法。

设网络点数为n，此时最小生成树的边数为n-1。

算法1 （克鲁斯凯尔，Kruskal）算法I的中心思想是每次添加权尽可能小的边，使新的图无圈，直到生成最小生成树为止。

也形象地简称“最小边的加入法”。

其步骤如下：（1）把N内的所有边按照权的非减次序排列。

（2）按（1）排列的次序检查N中的每一条边，如果这条边与已得到的边不产生圈，则取这一条边为解的一部分。

最小生成树的算法王洁引言：求连通图的最小生成树是数据结构中讨论的一个重要问题．在现实生活中，经常遇到如何得到连通图的最小生成树，求最小生成树不仅是图论的基本问题之一 ,在实际工作中也有很重要的意义，,人们总想寻找最经济的方法将一个终端集合通过某种方式将其连接起来 ,比如将多个城市连为公路网络 ,要设计最短的公路路线;为了解决若干居民点供水问题 ,要设计最短的自来水管路线等.而避开这些问题的实际意义 ,抓住它们的数学本质 ,就表现为最小生成树的构造。

下面将介绍几种最小生成树的算法。

一，用“破圈法”求全部最小生成树的算法1 理论根据1.1 约化原则给定一无向连通图 G =（V ,E ）（ V 表示顶点，E 表示边），其中 V={ 1v , 2v ,3v …… n v },E= { 1e , 2e , 3e …… n e }对于 G 中的每条边 e ∈ E 都赋予权ω（i e ）>0，求生成树 T = （V ,H ），H ⊆ E ，使生成树所有边权最小，此生成树称为最小生成树．（1） 基本回路将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝．将任一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为()cf e 。

基本回路是由 T 中的树枝和一条连枝构成的回路．（2） 基本割集设无向图 G 的割集 S （割集是把连通图分成两个分离部分的最少支路集合） ，若 S 中仅包含有T 中的一条树枝，则称此割集为基本割集，记为()S e 。

基本割集是集合中的元素只有一条是树枝，其他的为连枝．（3） 等长变换设T=(V,H),为一棵生成树，e ∈ H, 'e ∈ E, 'e ∉ H,当且仅当'e ∈()cf e ，也就是说e ∈()S e ，则'T =T ⊕{e, 'e }也是一棵生成树。

当()e ω='()e ω时，这棵生成树叫做等长变换。

Phyloviz（Phylogenetic Networks Visualization）是一种用于可视化和分析生物学系统进化关系的工具，通常用于展示物种、基因或其他生物实体之间的进化关系。

最小生成树（Minimum Spanning Tree，MST）是Phyloviz中一种用于呈现数据的方法，下面是对Phyloviz最小生成树的解读。

Phyloviz最小生成树解读步骤：1.数据准备：首先，你需要准备包含生物学实体之间进化关系的数据。

这通常是一种分子生物学的数据，例如基因序列或其他遗传信息。

2.输入数据到Phyloviz：将数据输入到Phyloviz中，并选择最小生成树作为展示数据的一种方式。

3.MST的构建： Phyloviz使用输入的数据构建一个最小生成树。

最小生成树是一种无向图，它连接了所有的节点，并且总权重最小。

在生物学的上下文中，节点通常代表不同的生物实体，边代表它们之间的进化关系。

4.节点和边的表示：在Phyloviz的最小生成树中，节点表示生物实体，边表示它们之间的进化关系。

通常，节点上可能包含有关生物实体的其他信息，例如物种名称、基因型等。

5.树的分析和解读：对生成的最小生成树进行分析和解读。

查看树的拓扑结构，了解节点之间的关系。

节点之间的距离可以表示它们之间的进化距离，这可以用于推测它们之间的共同祖先和演化关系。

6.进化路径和分支：最小生成树的分支和路径提供了有关生物实体进化路径的信息。

较短的分支表示较近的进化关系，而较长的分支表示较远的关系。

7.树的可视化： Phyloviz提供了直观的可视化界面，可以通过调整参数和样式来定制树的外观。

你可以选择不同的布局、颜色方案和标签显示方式，以便更好地呈现数据。

8.附加信息的显示： Phyloviz通常支持在树节点上显示额外的信息，例如置信度或其他测量。

这有助于进一步解释树的结构。

Phyloviz最小生成树的解读依赖于你的数据和问题背景。

无线传感器网络的网络拓扑控制方法无线传感器网络（Wireless Sensor Network, WSN）是由大量部署在被监测区域的节点组成的。

这些节点通过无线通信协作工作，以收集、处理和传输环境中的信息。

网络拓扑控制旨在优化网络的性能和可靠性，提高能源利用效率，延长节点寿命，并提供高质量的服务。

本文将探讨几种常用的无线传感器网络的网络拓扑控制方法。

一、平面拓扑控制方法1. 最小生成树（Minimum Spanning Tree, MST）MST是一种常用的平面拓扑控制方法，通过构建一棵最小生成树来减少无线传感器网络中的通信开销。

该方法中，首先选择一个起始节点，然后逐步添加与网络中已选择节点相连的最短边，直到所有节点都被添加进来。

最小生成树方法可以减少冗余通信和多路径传输，从而提高网络的可靠性和能源利用效率。

2. 重心生成树（Centroid-based Spanning Tree, CST）CST是一种以节点重心为基础的拓扑控制方法，该方法通过选择网络中节点的重心作为根节点，构建一棵生成树，来实现网络的平衡分布。

重心是指节点到网络中所有其他节点的距离之和最小的节点。

CST 能够降低能量消耗，减少网络中节点的通信开销，并提高网络的稳定性。

二、分层拓扑控制方法1. 分簇（Clustering）分簇是一种常用的分层拓扑控制方法，将网络中的节点划分为若干个簇，每个簇由一个簇头节点（Cluster Head）负责。

簇头节点负责接收和处理簇内节点的数据，并将聚合后的数据传输给基站（Base Station）。

该方法可以减少无线传感器网络中的通信开销，延长节点的寿命，并提高网络的可靠性。

2. 多跳传输（Multi-hop transmission）多跳传输是一种将节点之间的数据传输通过多个中间节点进行转发的拓扑控制方法。

该方法可以减少节点之间的直接通信距离，降低能量消耗，并提高网络的容错性。

多跳传输还可以增加网络的覆盖范围，提高网络的可扩展性。