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

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下標(biāo)存放節(jié)點,數(shù)組值存放權(quán)值。比如(1,2)有邊,權(quán)值為3,則graph[1][2]=3,同時graph[2][1]=3,沒有邊的點用INF(無窮大)表示咯。
2.如何判斷和最近的點,由于每一次進(jìn)來都會改變情況,所以每次都要更新,我們用一個一元數(shù)組opt[n]來表示,數(shù)組下標(biāo)表示節(jié)點號,值表示該節(jié)點到U的最短距離。記住,加入到U集合的點是不用再管它的了,所以,我們還要設(shè)置一個數(shù)組flag[n],來設(shè)置標(biāo)志位,看是否已經(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;
    }

  }

}

因為代碼是自己當(dāng)場寫出來,寫出來和原來正確代碼相比較了,如果讀者發(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>
            欧美日韩在线视频一区| 国产精品视频福利| 亚洲国产另类精品专区| 国产综合色一区二区三区| 午夜一区在线| 亚洲欧美日韩在线不卡| 免费观看国产成人| 蜜桃伊人久久| 91久久国产精品91久久性色| 亚洲欧美激情视频| 亚洲一区二区三区高清不卡| 好看的日韩视频| 亚洲高清免费在线| 在线亚洲电影| 久久精品视频免费观看| 99re6这里只有精品| 国产日产欧美一区| 1769国内精品视频在线播放| 欧美日韩中文在线观看| 久久国产精品亚洲va麻豆| 亚洲三级毛片| 亚洲一区二区在线观看视频| 亚洲国产精品va| 在线一区二区日韩| 久久精品亚洲一区| 欧美午夜精品伦理| 亚洲国产高清在线观看视频| 国产日本欧洲亚洲| 亚洲精品欧美极品| 久久精品国产第一区二区三区| 亚洲欧洲精品一区二区三区不卡 | 亚洲精品视频二区| 亚洲小少妇裸体bbw| 在线看不卡av| 亚洲伊人网站| 亚洲国产色一区| 先锋影音久久久| 亚洲自拍高清| 99国产麻豆精品| 久久久免费观看视频| 一区二区三区日韩| 久久精品国产77777蜜臀| 亚洲免费在线| 亚洲国产欧美国产综合一区 | 国产精品影院在线观看| 欧美黑人多人双交| 国产一区清纯| 欧美一级播放| 亚洲午夜未删减在线观看| 一本综合精品| 欧美暴力喷水在线| 伊人久久婷婷| 久久亚洲不卡| 久久九九电影| 国产视频欧美视频| 久久精品国产2020观看福利| 久久综合九九| 欧美专区在线观看| 国产欧美三级| 久久岛国电影| 久久9热精品视频| 国产一区二区三区在线观看精品| 国产亚洲激情在线| 亚洲男人的天堂在线aⅴ视频| 亚洲欧美国产另类| 一本色道婷婷久久欧美| 亚洲欧美综合v| 国产精品欧美在线| 欧美一区二区三区视频免费播放| 欧美在线视频免费观看| 久久久久久久久蜜桃| 另类亚洲自拍| 两个人的视频www国产精品| 欧美激情一区二区三区成人| 欧美亚洲成人免费| 亚洲伊人伊色伊影伊综合网| 久久久精品国产一区二区三区 | 欧美不卡视频一区发布| 欧美高清视频一区二区| 亚洲国产黄色片| 欧美不卡视频| 一区二区三区视频观看| 久久精品国产综合| 久久精品论坛| 日韩特黄影片| 亚洲午夜影视影院在线观看| 久久综合狠狠| 亚洲成人影音| 99ri日韩精品视频| 欧美高清在线观看| 欧美日韩亚洲国产一区| 欧美日韩亚洲视频| 亚洲一区二区三区四区视频 | 亚洲天堂免费在线观看视频| 欧美一区二区三区视频免费| 亚洲国产综合91精品麻豆| 亚洲欧美福利一区二区| 久久综合免费视频影院| 国产精品捆绑调教| 久久艳片www.17c.com| 99精品免费视频| 国产拍揄自揄精品视频麻豆| 日韩天堂av| 欧美一区二区三区免费视| 欧美日韩午夜视频在线观看| 一区免费观看视频| 亚洲精品综合| 极品裸体白嫩激情啪啪国产精品 | 老司机午夜精品| 欧美精品一区二区三区在线看午夜 | 国产亚洲综合性久久久影院| 野花国产精品入口| 亚洲欧美日本另类| 亚洲九九九在线观看| 久久免费国产| 国产精品乱码一区二三区小蝌蚪 | av成人手机在线| 欧美一区国产在线| 亚洲影院免费观看| 欧美激情第8页| 久久躁日日躁aaaaxxxx| 欧美在线视频在线播放完整版免费观看 | 久久久水蜜桃av免费网站| 欧美视频在线一区| 欧美成人精品一区二区| 久热精品视频在线| 久久黄色网页| 国产伦理一区| aa成人免费视频| 日韩小视频在线观看专区| 亚洲精品一区二区三区蜜桃久| 久久综合九色综合久99| 在线观看精品一区| 香蕉久久国产| 久久成人在线| 国内免费精品永久在线视频| 亚洲天天影视| 久久久噜噜噜久久中文字免| 国产真实精品久久二三区| 亚洲欧美日韩在线不卡| 亚洲午夜久久久久久久久电影院| 欧美日韩综合在线| 亚洲人成在线免费观看| 欧美日韩一区二区三区视频| 亚洲午夜激情在线| 欧美日韩成人一区| 亚洲美女黄色| 亚洲特级毛片| 欧美色综合天天久久综合精品| 午夜视频在线观看一区二区三区| 亚洲午夜视频| 欧美一区成人| 国产亚洲综合精品| 久久天天狠狠| 欧美激情免费观看| 亚洲精品免费在线观看| 午夜国产精品影院在线观看| 激情一区二区| 久久久久免费视频| 亚洲福利在线看| 一区二区三区.www| 国产精品久久久久久久午夜片| 久久尤物视频| 亚洲人成网站在线观看播放| 一区二区三区国产在线观看| 国产色视频一区| 久久久久久一区二区| 亚洲另类春色国产| 欧美好骚综合网| 亚洲一区二区三区高清不卡| 激情另类综合| 欧美激情综合亚洲一二区| 久久精品成人欧美大片古装| 久久日韩精品| 亚洲欧洲一区| 久久久97精品| 一区二区三区精品视频| 久久久久国产成人精品亚洲午夜| 亚洲精品小视频在线观看| 校园春色国产精品| 免费在线欧美黄色| 亚洲一区亚洲二区| 亚洲国产精品小视频| 午夜精品久久久久久久蜜桃app| 亚洲国产精品第一区二区三区| 亚洲小说欧美另类婷婷| 亚洲高清视频一区| 欧美视频在线观看免费网址| 欧美激情第二页| 午夜亚洲精品| 日韩视频免费观看| 国产一区二区三区在线观看精品| 亚洲在线中文字幕| 欧美国产日韩精品免费观看| 韩日精品视频一区| 欧美理论大片| 久久综合伊人77777尤物| 美女主播一区| 性色av香蕉一区二区| 国产精品电影观看|