bwin56必赢手机版算法导论学习-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算法的推行步骤:

bwin56必赢手机版 1

若是达到图所出示有6个驻地,除了第一单吃我方占据外,其余都是敌方势力。根据prim算法,我们先是找到距离1号军事基地最近底基地3进行武力打击(1-3离开也1,,1-2离bwin56必赢手机版也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 }

 

admin

网站地图xml地图