MST在前面学习了Kruskal算法,还有一种算法叫做Prim的。这两者的区别是Prim算法适合稠密图,比如说鸟巢这种几乎所有点都有相连的图。其时间复杂度为O(n^2),其时间复杂度与边的数目无关;而kruskal算法的时间复杂度为O(eloge),跟边的数目有关,适合稀疏图。
prim算法
基本思想:假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={ 空集 }开始。重复执行下列操作:
1.在所有u∈U,v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE中,同时v0并入U,直到V=U为止;接下里以 v0为边的起点,继续寻找权值最小的边并入集合TE中,依次往复;
2.最后,TE中必有n-1条边,T=(V,TE)为G的最小生成树。
Prim算法的核心:始终保持TE中的边集构成一棵生成树,也就是它与Kruskal算法的主要区别是,Prim是一直保持一种串联的状态而不遵从整体的贪心算法。其实初始点uo的选择可以随意,一般做题题目条件会给出或者取最小的权值边。
其实现的代码如下:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define infinity 1000000
#define max_vertexes 6
typedef int Graph[max_vertexes][max_vertexes];
void prim(Graph G,int vcount,int father[])
{
int i,j,k;
int lowcost[max_vertexes];
int closeset[max_vertexes],used[max_vertexes];
int min;
for (i=0;i<vcount;i++)
{
/* 最短距离初始化为其他节点到1号节点的距离 */
lowcost[i]=G[0][i];
/* 标记所有节点的依附点皆为默认的1号节点 */
closeset[i]=0;
used[i]=0;
father[i]=-1;
}
used[0]=1; /*第一个节点是在s集合里的*/
/* vcount个节点至少需要vcount-1条边构成最小生成树 */
for (i=1;i<=vcount-1;i++)
{
j=0;
min = infinity;
/* 找满足条件的最小权值边的节点k */
for (k=1;k<vcount;k++)
/* 边权值较小且不在生成树中 */
if ((!used[k])&&(lowcost[k]<min))
{
min = lowcost[k];
j=k;
}
father[j]=closeset[j];
printf("%d %d\n",j+1,closeset[j]+1);//打印边
used[j]=1;;//把第j个顶点并入了U中
for (k=1;k<vcount;k++)
/* 发现更小的权值 */
if (!used[k]&&(G[j][k]<lowcost[k]))
{
lowcost[k]=G[j][k];/*更新最小权值*/
closeset[k]=j;;/*记录新的依附点*/
}
}
}
int main()
{
FILE *fr;
int i,j,weight;
Graph G;
int fatheer[max_vertexes];
for(i=0; i<max_vertexes; i++)
for(j=0; j<max_vertexes; j++)
G[i][j] = infinity;
fr = fopen("prim.txt","r");
if(!fr)
{
printf("fopen failed\n");
exit(1);
}
while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF)
{
G[i-1][j-1] = weight;
G[j-1][i-1] = weight;
}
prim(G,max_vertexes,fatheer);
return 0;
}
邻接矩阵的形式进行存储的实现:
#include <stdio.h>
#define n 6
#define MaxNum 10000 /*定义一个最大整数*/
/*定义邻接矩阵类型*/
typedef int adjmatrix[n+1][n+1]; /*0号单元没用*/
typedef struct{
int fromvex,tovex;
int weight;
}Edge;
typedef Edge *EdgeNode;
int arcnum; /*边的个数*/
/*建立图的邻接矩阵*/
void CreatMatrix(adjmatrix GA){
int i,j,k,e;
printf("图中有%d个顶点\n",n);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(i==j){
GA[i][j]=0; /*对角线的值置为0*/
}
else{
GA[i][j]=MaxNum; /*其它位置的值置初始化为一个最大整数*/
}
}
}
printf("请输入边的个数:");
scanf("%d",&arcnum);
printf("请输入边的信息,按照起点,终点,权值的形式输入:\n");
for(k=1;k<=arcnum;k++){
scanf("%d,%d,%d",&i,&j,&e); /*读入边的信息*/
GA[i][j]=e;
GA[j][i]=e;
}
}
/*初始化图的边集数组*/
void InitEdge(EdgeNode GE,int m){
int i;
for(i=1;i<=m;i++){
GE[i].weight=0;
}
}
/*根据图的邻接矩阵生成图的边集数组*/
void GetEdgeSet(adjmatrix GA,EdgeNode GE){
int i,j,k=1;
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
if(GA[i][j]!=0&&GA[i][j]!=MaxNum){
GE[k].fromvex=i;
GE[k].tovex=j;
GE[k].weight=GA[i][j];
k++;
}
}
}
}
/*按升序排列图的边集数组*/
void SortEdge(EdgeNode GE,int m){
int i,j,k;
Edge temp;
for(i=1;i<m;i++){
k=i;
for(j=i+1;j<=m;j++){
if(GE[k].weight>GE[j].weight){
k=j;
}
}
if(k!=i){
temp=GE[i];GE[i]=GE[k];GE[k]=temp;
}
}
}
/*利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树*/
void Prim(adjmatrix GA,EdgeNode T){
int i,j,k,min,u,m,w;
Edge temp;
/*给T赋初值,对应为v1依次到其余各顶点的边*/
k=1;
for(i=1;i<=n;i++){
if(i!=1){
T[k].fromvex=1;
T[k].tovex=i;
T[k].weight=GA[1][i];
k++;
}
}
/*进行n-1次循环,每次求出最小生成树中的第k条边*/
for(k=1;k<n;k++){
min=MaxNum;
m=k;
for(j=k;j<n;j++){
if(T[j].weight<min){
min=T[j].weight;m=j;
}
}
/*把最短边对调到k-1下标位置*/
temp=T[k];
T[k]=T[m];
T[m]=temp;
/*把新加入最小生成树T中的顶点序号赋给j*/
j=T[k].tovex;
/*修改有关边,使T中到T外的每一个顶点保持一条到目前为止最短的边*/
for(i=k+1;i<n;i++){
u=T[i].tovex;
w=GA[j][u];
if(w<T[i].weight){
T[i].weight=w;T[i].fromvex=j;
}
}
}
}
/*输出边集数组的每条边*/
void OutEdge(EdgeNode GE,int e){
int i;
printf("按照起点,终点,权值的形式输出的最小生成树为:\n");
for(i=1;i<=e;i++){
printf("%d,%d,%d\n",GE[i].fromvex,GE[i].tovex,GE[i].weight);
}
}
void main(){
adjmatrix GA;
Edge GE[n*(n-1)/2],T[n];
CreatMatrix(GA);
InitEdge(GE,arcnum);
GetEdgeSet(GA,GE);
SortEdge(GE,arcnum);
Prim(GA,T);
printf("\n");
OutEdge(T,n-1);
}
分享到:
相关推荐
最小生成树的prim算法.可导入多种文件计算
Prim算法(普里姆算法),是1930年捷克数学家算法沃伊捷赫·亚尔尼克(Vojtěch Jarník)最早设计; 1957年,由美国计算机科学家罗伯特·普里姆独立实现; 1959年,艾兹格·迪科斯彻再次发现了该算法。 Prim算法...
最小生成树,使用PRIM方法生成最小生成树。
最小生成树(MST)问题
最小生成树 (MST),已被广泛用于广泛的科学领域与日常生活中,例如 粒子物理学(区分对撞机碰撞中的事件类别)、天文学(探测星团中的质量分离)、导航路线计算,近几年也不断有新的最小生成树算法被提出,在新的...
输入:城市个数N 输出:建设通信网络的结构和最低成本(距离即成本) 说明:主函数调用prepare函数准备城市坐标及各城市间距离等数据,并调用最小生成树算法primMST primMST算法根据城市网络图获得最小生成树
本文中,我们提出一种新的全分布式算法来在一般的通讯网络中构造一棵最小生成树(MST)。在执行过程中,算法维系着一个跨所有组成员的不相交的树集。每棵树最初只由一个节点构成,每棵树独立的通过连接最近的树进行...
Prim算法是一种用于找到无向图的最小生成树(Minimum Spanning Tree, MST)的贪婪算法。MST是一个包含所有图节点的子图,使得子图中的边权重之和最小。Prim算法从一个起始节点开始,然后逐步扩展这个子图,直到包含...
Boruvka算法用于查找边加权图的最小生成树(MST),它早于Prim和Kruskal的算法,但仍然可以被认为是两者的关联。1926年,奥塔卡·博鲁夫卡(Otakar Boruvka)首次提出了一种求给定图的MST的方法。这在计算机出现之前...
一种新的最小生成树算法,罗竣友,尤众,本文提出一种新的算法以完成加权连通图的最小生成树(minimum spanning tree, MST)。该算法具有以下优点:1,由于主要以排序为主,因此比较�
数学建模常用经典算法集合均已成功编译-最小生成树算法MSTA.rar 数学建模常用经典算法集合(均已成功编译) 有偿代做,如有需要请联系QQ 1170906655,中介勿扰! 层次分析算法AHP.rar ...
输入矩阵是边加权矩阵,未连接的边被指定为 0 >>A = [0 192 344 0 0 0 0 0 0 0 0; 192 0 309 0 555 0 0 0 0 0 0; 344 309 0 499 0 0 0 0 0 0 0; 0 0 499 0 840 0 229 286 0 0 0; 0 555 0 840 0 237 0 0 0 0 0;...
[摘要] 选择一颗生成树,使之总的消费最少,也就是要构造连通网的最小代价生成树(简称为最小生成树)的问题,一颗生成树的代价就是树上各边的代价之和,构造最小生成树可以有多种算法,其中多数算法利用了MST的性质...
C#,最小生成树(MST)克鲁斯卡尔(Kruskal)算法的源代码。克鲁斯卡尔(Kruskal)算法是一种用来寻找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都...
使用两种最小生成树的方法进行聚类,并对效果进行比较,处理了8种典型二维图像和压缩后的三维图像
自己写的最小生成树算法,请自己在同一个目录下建立一个gtest。txt的文件。 然后编译,这是在linux下写的,应该移植没有问题 C语言写的
数据结构:C++语言实现最小生成树的算法。
最小生成树(MST):权值最小的生成树。 生成树和最小生成树的应用:要连通n个城市需要n-1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。 构造网的最小生成树必须解决下面两...
各种应用通常要求图模型中的每条表与权重或者开销关联起来。在航空地图中,每一条边表示一条...我们可以用查找最小生成树来表示像第一类这样的无向图,这也是本文重点所要介绍的加权无向图以及最小生成树(MST)算法。
网络最小生成树算法,利用numpy实现,MST 矩阵模型