青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

yuanyuelang

常用鏈接

統(tǒng)計

最新評論

最小生成樹之Prim算法

最小生成樹是圖論的一個重要部分,解決這個問題的算法主要有Kruskal算法和Prim算法。

最小生成樹:顧名思義是一棵樹,該樹是圖中權(quán)值和最小的。

這篇文章介紹Prim算法,Kruskal算法請參閱最小生成樹之Kruskal算法

Prim算法的主要思路:
1.圖G={V,E},V表示節(jié)點集,E表示邊集,初始時將V0從V中拿出,放入空集合U中,U={V0},T(E)空
2.選擇和集合U有連接的且最近的點Vx(在V中),放入U,U={V0,Vx},并將邊加入到T(E)中。
3.重復(fù)第二步,直到U=V
很明顯需要n-1步,n為圖的節(jié)點數(shù)。

現(xiàn)在我們就是要如何把它變成代碼的問題了。
1.存儲問題,我們需要一個二元數(shù)組graph下標存放節(jié)點,數(shù)組值存放權(quán)值。比如(1,2)有邊,權(quán)值為3,則graph[1][2]=3,同時graph[2][1]=3,沒有邊的點用INF(無窮大)表示咯。
2.如何判斷和最近的點,由于每一次進來都會改變情況,所以每次都要更新,我們用一個一元數(shù)組opt[n]來表示,數(shù)組下標表示節(jié)點號,值表示該節(jié)點到U的最短距離。記住,加入到U集合的點是不用再管它的了,所以,我們還要設(shè)置一個數(shù)組flag[n],來設(shè)置標志位,看是否已經(jīng)加入到U集合了。
3.這樣的話大功也就告成了,一般就會寫了吧。如果要保存各個邊的話,還要添加一個數(shù)組line[n]來表示節(jié)點到U的最短距離到底是連接U中哪一個節(jié)點的。

看看代碼,分析分析吧。。記住很重要的,自己舉個例子看看。最后一定要熟練掌握其原理,并且快速的寫出代碼。
#define MAXN 100
#define INF 0xfffffff

int result_s[MAXN],result_e[MAXN];//保存邊

void prim(int graph[MAXN][MAXN],int opt[],int n)
{
  
int i,j,min,vertex,line[n];
  
bool flag[n];
 
  
for(i=0;i<n;i++)//初始化
    opt[i]=graph[0][i];
    line[i]
=0;
    flag[i]
=false;
   }

  flag[
0]=true;
  
for(i=1;i<n;i++){
    min
=INF;
    
for(j=1;j<n;j++){
      
if(!flag[j]&&opt[j]<min){//選擇最優(yōu)點
        min=opt[j];
        vertex
=j;
      }

    }

    flag[vertex]
=true//加入到U集合
    result_s[i]=line[vertex];//保存
    result_e[i]=vertex;
    
for(j=1;j<n;j++){//更新
      if(!flag[j]&&graph[vertex][j]<opt[j])
         opt[j]
=graph[vertex][j];
         line[j]
=vertex;
    }

  }

}

因為代碼是自己當場寫出來,寫出來和原來正確代碼相比較了,如果讀者發(fā)現(xiàn)有錯,還望指正。
我想我們就是要鍛煉這種寫代碼的能力,不能太依靠模板,不然忘得快。
注意:最后結(jié)果都知道了,opt[]保存的是最小生成樹的選入的各個邊的權(quán)值,result_s[]和result_e保存了到底是哪些點組成的最小生成樹。

















posted on 2009-09-14 18:47 原語餓狼 閱讀(533) 評論(0)  編輯 收藏 引用 所屬分類: 圖論

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产精品成人一区二区| 欧美日韩xxxxx| 免费一区视频| 国产亚洲电影| 一区二区三区日韩精品| 久久在线免费| 性色一区二区| 国产精品亚洲综合久久| 亚洲一区久久久| 黑人巨大精品欧美一区二区| 亚洲一区二区在线免费观看视频 | 欧美高清视频一区二区| 午夜精品福利在线| 国产精品视频yy9099| 亚洲欧美bt| 亚洲自拍偷拍色片视频| 国产精品女主播在线观看| 亚洲一区免费看| 亚洲午夜高清视频| 国产精品无码永久免费888| 午夜精品久久久久久99热软件| 日韩一级大片| 欧美色另类天堂2015| 亚洲免费在线视频一区 二区| 亚洲无吗在线| 国产亚洲美州欧州综合国| 久久久久国产免费免费| 久久久久国产一区二区三区| 影音先锋中文字幕一区二区| 欧美激情视频在线免费观看 欧美视频免费一 | 欧美激情小视频| 一区二区三区欧美在线观看| 亚洲天堂免费观看| 韩国av一区二区| 亚洲国产精品v| 欧美成人第一页| 亚洲性视频h| 午夜宅男久久久| 亚洲成在线观看| 日韩香蕉视频| 国内精品久久久久影院薰衣草| 欧美成人免费va影院高清| 欧美精品一区二区久久婷婷| 亚洲欧美日韩综合| 久久影音先锋| 亚洲欧美日韩一区二区三区在线观看 | 欧美一区国产一区| 亚洲精品久久久久中文字幕欢迎你| 亚洲精品国产精品国产自| 国产精品成人aaaaa网站 | 久久丁香综合五月国产三级网站| 亚洲国产高潮在线观看| 一本色道久久综合狠狠躁篇怎么玩| 国产目拍亚洲精品99久久精品 | 午夜免费在线观看精品视频| 久久天堂av综合合色| 在线视频日韩精品| 久久久久国产精品厨房| 亚洲一级二级| 免费不卡在线视频| 久久aⅴ国产欧美74aaa| 欧美人在线观看| 美女久久一区| 国产精品日韩在线播放| 亚洲国产婷婷香蕉久久久久久99| 国产日韩欧美精品综合| 夜夜嗨av一区二区三区| 亚洲激情视频在线播放| 久久99伊人| 性欧美xxxx大乳国产app| 欧美不卡高清| 每日更新成人在线视频| 国产欧美日韩在线视频| 亚洲人精品午夜| 在线精品高清中文字幕| 午夜性色一区二区三区免费视频| 一区二区三区久久| 欧美国产欧美亚州国产日韩mv天天看完整 | 亚洲激情另类| 久久久久国产一区二区三区| 久久九九国产| 国产女精品视频网站免费 | 欧美一级欧美一级在线播放| 亚洲一区二区三区乱码aⅴ| 欧美.www| 欧美高清在线一区二区| 一区精品久久| 久久精品综合网| 久久久91精品| 国产午夜精品全部视频在线播放 | 欧美三级视频在线观看| 亚洲欧洲另类国产综合| 亚洲日本在线观看| 免费中文字幕日韩欧美| 男人的天堂亚洲| 亚洲国产精品综合| 蜜桃伊人久久| 亚洲国产综合在线| 一区二区国产日产| 欧美日韩美女| 在线视频精品| 欧美亚洲视频一区二区| 国产欧美一区二区精品性 | 国产精品区免费视频| 亚洲视频第一页| 性色av一区二区三区| 国产美女精品免费电影| 欧美影院成人| 免费观看不卡av| 亚洲精品久久久久久下一站 | 久久久久九九视频| 在线观看欧美成人| 欧美精品免费看| 久久激情视频久久| 国内揄拍国内精品少妇国语| 久久人人97超碰精品888| 亚洲福利视频免费观看| 在线性视频日韩欧美| 国产精品老牛| 久久久99国产精品免费| 亚洲国产精品久久久久婷婷884| 一区二区三区日韩欧美| 国产日韩久久| 欧美电影资源| 亚洲欧美日韩在线播放| 欧美成人高清视频| 一区二区三区精品在线| 国产在线视频欧美一区二区三区| 美国十次了思思久久精品导航| 日韩一级片网址| 久久久久久自在自线| 日韩亚洲综合在线| 国产在线观看91精品一区| 欧美国产乱视频| 欧美制服第一页| 亚洲另类在线一区| 久久日韩粉嫩一区二区三区| 在线亚洲精品| 亚洲第一福利视频| 国产精品一区二区久久久久| 欧美成年视频| 久久精品72免费观看| av成人免费| 欧美高清hd18日本| 久久精品国产亚洲高清剧情介绍| 亚洲毛片在线观看| 国内久久精品视频| 国产精品免费小视频| 欧美黑人一区二区三区| 久久久精品国产免大香伊| 在线视频日本亚洲性| 亚洲欧洲另类| 亚洲大胆人体视频| 久久国产精品久久久久久| 亚洲精品久久久久久下一站| 黄色成人av在线| 国产精品一区二区三区四区| 欧美日韩免费一区二区三区| 美女主播精品视频一二三四| 性欧美暴力猛交69hd| 正在播放日韩| 日韩一级精品| 亚洲伦理久久| 91久久精品国产91久久性色| 麻豆成人在线观看| 欧美在线一区二区| 午夜视频在线观看一区二区| 亚洲——在线| 亚洲天堂网在线观看| 999亚洲国产精| 99re66热这里只有精品3直播| 亚洲精品视频二区| 亚洲日本中文| 亚洲精品在线免费| 亚洲精品一区二区三区樱花| 91久久精品视频| 亚洲人成网站999久久久综合| 亚洲国产日韩在线一区模特| 亚洲电影第1页| 亚洲第一综合天堂另类专| 亚洲国产99精品国自产| 亚洲国产精品精华液2区45| 亚洲黄色免费| 亚洲毛片一区二区| 亚洲专区一区| 久久成人国产精品| 老司机免费视频久久| 欧美不卡在线| 亚洲人成在线观看网站高清| 一本色道久久综合亚洲精品小说| 亚洲精品在线观| 亚洲神马久久| 亚洲成色777777女色窝| 91久久精品国产91性色tv| 亚洲高清久久久| 日韩亚洲欧美中文三级| 亚洲欧美日韩精品久久久久| 久久国产欧美日韩精品| 免费成人av资源网| 欧美视频免费在线|