算法导论学习-prim算法
一. 关于最小生成树
对于无向连通图G=(V,E),其中V表示图的顶点,E表示图的边,对于每条边都有一个权值,可以理解为边a->b的权值C为从a走到b要走的路程为C。现在我们希望找到一个无回路的子集T,且有T是E的子集,T连接了所有的顶点,且其权值和最小。那么这样一个子图G‘=(V,T)称之为图G的最小生成树。
二. 最小生成树的基本性质
最小生成树的边数|T|必然服从|T|=|V|-1.
最小生成树不可以有循环
最小生成树不必是唯一的。
三. Prim算法
对于最小生成树有两种算法:prim算法和kruskal算法,这里只说prim算法。prim算法的核心是两个动态集合U和V-U。这里为了说明的更为生动一些,我用军事入侵的方式来说明prim算法的操作过程。假设有一个我方军事基地,假设该军事基地编号为1(根据不同情况可以改变),其他n-1个军事基地是敌方军事武装所在地。又假设我方军事力量空前强大,逮谁灭谁(意淫一下),但就算这样,我们也不想耗费不必要的力量(这里可以理解为不想走多余的路),我方军队想要设计一套行军路线,是的总的行军路线里程最小并且消灭完所有的地方军事武装。下面以图为例说明prim算法的执行步骤:
如上图所示有6个军事基地,除了第一个被我方占据外,其余都是敌方势力。根据prim算法,我们首先找到距离1号军事基地最近的军事基地3进行军事打击(1-3距离为1,,1-2距离为6,1-4距离为5)。在占领3号基地以后,我们继续找距离红色标注基地最近的基地,可以发现6号基地距离{1,3}为4,为最近基地。所以我方将6号基地作为下一打击对象。占领6号以后,发现4号基地距离{1,3,6}为2,为最近基地,所以4号基地为下一占领基地。相似的,e,f图依次类推。
下面附上完整代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int max_size=50; 6 const int inf=1<<30; 7 int map[max_size][max_size]; 8 struct edge{ 9 int c,flag; 10 }edge[max_size*max_size/2]; 11 int n,m; 12 int prim(){ 13 int s=1,sum=0; 14 for(int i=1;i<=n;i++){ 15 if(i==s) continue; 16 edge[i].c=map[s][i]; 17 edge[i].flag=0; 18 } 19 edge[s].flag=1; 20 edge[s].c=0; 21 22 for(int k=1;k<=n-1;k++){//loop n-1 times 23 int mmin=inf,flag=0,nearest; 24 for(int i=1;i<=n;i++){ 25 if(!edge[i].flag&&edge[i].c<mmin){ 26 mmin=edge[i].c; 27 flag=1; 28 nearest=i; 29 } 30 } 31 if(!flag) return -1; 32 edge[nearest].flag=1; 33 sum+=mmin; 34 for(int i=1;i<=n;i++){ 35 if(!edge[i].flag&&edge[i].c>map[nearest][i]){ 36 edge[i].c=map[nearest][i]; 37 } 38 } 39 } 40 return sum; 41 } 42 int main(){ 43 while(scanf("%d%d",&n,&m)!=EOF){ 44 int a,b,c; 45 memset(map,inf,sizeof(map)); 46 for(int i=1;i<=m;i++){ 47 scanf("%d%d%d",&a,&b,&c); 48 map[a][b]=map[b][a]=c; 49 } 50 if(prim()) printf("%d\n",prim()); 51 else printf("fail\n"); 52 } 53 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。