当前位置:首页 » 操作系统 » prim求最小生成树算法

prim求最小生成树算法

发布时间: 2025-01-17 22:23:29

① 什么是Prim算法

Prim算法
Prim算法用于求无向图的最小生成树

设图G =(V,E),其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素,则结束,否则继续执行②。
其算法的时间复杂度为O(n^2)

Prim算法实现:
(1)集合:设置一个数组set[i](i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中(注意:顶点号与下标号差1)
(2)图用邻接阵表示,路径不通用无穷大表示,在计算机中可用一个大整数代替。

参考程序

/* Prim.c

Copyright (c) 2002, 2006 by ctu_85

All Rights Reserved.

*/

/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */

#include "stdio.h"

#define maxver 10

#define maxright 100

int main()

{

int G[maxver][maxver],in[maxver]=,path[maxver][2];

int i,j,k,min=maxright;

int v1,v2,num,temp,status=0,start=0;

restart:

printf("Please enter the number of vertex(s) in the graph:\n");

scanf("%d",&num);

if(num>maxver||num<0)

{

printf("Error!Please reinput!\n");

goto restart;

}

for(j=0;j<num;j++)

for(k=0;k<num;k++)

{

if(j==k)

G[j][k]=maxright;

else

if(j<k)

{

re:

printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);

scanf("%d",&temp);

if(temp>=maxright||temp<-1)

{

printf("Invalid input!\n");

goto re;

}

if(temp==-1)

temp=maxright;

G[j][k]=G[k][j]=temp;

}

}

for(j=0;j<num;j++)

{

status=0;

for(k=0;k<num;k++)

if(G[j][k]<maxright)

{

status=1;

break;

}

if(status==0)

break;

}

do

{

printf("Please enter the vertex where Prim algorithm starts:");

scanf("%d",&start);

}while(start<0||start>num);

in[start-1]=1;

for(i=0;i<num-1&&status;i++)

{

for(j=0;j<num;j++)

for(k=0;k<num;k++)

if(G[j][k]<min&&in[j]&&(!in[k]))

{

v1=j;

v2=k;

min=G[j][k];

}

if(!in[v2])

{

path[i][0]=v1;

path[i][1]=v2;

in[v1]=1;

in[v2]=1;

min=maxright;

}

}

if(!status)

printf("We cannot deal with it because the graph is not connected!\n");

else

{

for(i=0;i<num-1;i++)

printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);

}

return 1;

}

Prim算法。

设图G =(V,E),其生成树的顶点集合为U。

①、把v0放入U。

②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树。

③、把②找到的边的v加入U集合。如果U集合已有n个元素,则结束,否则继续执行②。

其算法的时间复杂度为O(n^2)

参考程序

//Prim 算法 读入顶点数(n)、边数(m),边的起始点和权值 用邻接矩阵储存

//例如

//7 12 (7个顶点12条边)

//1 2 2

//1 4 1

//1 3 4

//2 4 3

//2 5 10

//3 4 2

//4 5 7

//3 6 5

//4 6 8

//4 7 4

//5 7 6

//6 7 1

#include <stdio.h>

#include <string.h>

int main()

{

int m , n;

int a[201][201] , mark[201] , pre[201] , dist[201];

int s , t , w;

int i , j , k , min , tot;

freopen("Prim.txt" , "r" , stdin);

//读入数据

memset(a , 0 , sizeof(a));

scanf("%d %d" , &n , &m);

for (i = 0; i < m; i ++)

{

scanf("%d %d %d" , &s , &t , &w);

a[s][t] = w; a[t][s] = w;

}

//赋初值

memset(mark , 0 , sizeof(mark));

memset(pre , 0 , sizeof(pre));

memset(dist , 9999 , sizeof(dist));

dist[1] = 0;

//Prim

for (i = 1; i <= n; i ++)

{

min = 9999; k = 0;

for (j = 1; j <= n; j ++)

if ((mark[j] == 0) && (dist[j] < min)) {min = dist[j]; k = j;}

if (k == 0) break;

mark[k] = 1;

for (j = 1; j <= n; j ++)

if ((mark[j] == 0) && (a[k][j] < dist[j]) && (a[k][j] > 0))

{

dist[j] = a[k][j];

pre[j] = k;

}

}

tot = 0;

for (i = 1; i <= n; i ++) tot += dist[i];

printf("%d\n" , tot);

return 0;

}

② 图所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树.

•普里姆(Prim)算法

基本思想

假设N=(V,E)是一个具有n个顶点的连通网,T=(U,TE)是所求的最小生成树,其中U是T的顶点集,TE是T的边集。

(1)初始U={u0}(u0∈V),TE=φ;

(2)在所有u∈U,v∈V-U的边中选一条代价最小的边(u0,v0)并入集合TE,同时将v0并入U;

(3)重复(2),直到U=V为止。

此时,TE中必含有n-1条边,则T=(V,{TE})为N的最小生成树。

注意:1.最小生成树不唯一。

2.该图从节点最小开始。

热点内容
安卓手机收藏的东西在哪里找 发布:2025-01-18 04:16:19 浏览:7
安卓手机网络无法使用怎么办 发布:2025-01-18 04:12:55 浏览:363
摩斯密码的杠是什么 发布:2025-01-18 04:06:52 浏览:808
winsock搜服务器ip 发布:2025-01-18 03:49:32 浏览:393
安卓手机蓝牙默认地址在哪里 发布:2025-01-18 03:47:57 浏览:906
shell脚本文件路径 发布:2025-01-18 03:40:31 浏览:483
sql语句执行错误 发布:2025-01-18 03:21:49 浏览:651
数据库双引号 发布:2025-01-18 03:10:20 浏览:79
学java和php 发布:2025-01-18 03:01:03 浏览:452
怎么开服务器的端口 发布:2025-01-18 02:54:23 浏览:648