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

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>
            亚洲欧美久久久久一区二区三区| 亚洲一区二区免费| 欧美一区二区精品久久911| 欧美va亚洲va香蕉在线| 欧美一二三区在线观看| 国产精品福利片| 亚洲一区二区三区激情| 一本色道久久综合| 欧美性色综合| 亚洲伊人网站| 一本久道久久久| 欧美日产国产成人免费图片| 亚洲精品国产系列| 亚洲激情在线观看视频免费| 久久精品国产亚洲aⅴ| 国产亚洲综合性久久久影院| 久久精品天堂| 裸体一区二区| av不卡免费看| 亚洲永久视频| 影音先锋在线一区| 亚洲第一区中文99精品| 欧美日韩精品在线| 午夜精品美女自拍福到在线| 午夜久久tv| 亚洲观看高清完整版在线观看| 欧美激情导航| 欧美三级午夜理伦三级中视频| 亚洲一区二区三区精品在线观看| 亚洲一区二区免费视频| 韩国av一区二区| 亚洲国产婷婷香蕉久久久久久99 | 亚洲精品乱码久久久久久久久| 欧美精品一区二区三区在线播放 | 国产精品午夜电影| 久久视频一区| 欧美日韩不卡一区| 欧美专区18| 欧美激情一二区| 欧美在线高清视频| 蜜桃av综合| 亚洲欧美日韩国产精品 | 亚洲人成亚洲人成在线观看图片| 91久久久久久久久| 国产在线播放一区二区三区| 国产精品一区二区久久久| 巨乳诱惑日韩免费av| 欧美激情一区二区三区蜜桃视频| 亚洲欧洲av一区二区| 麻豆九一精品爱看视频在线观看免费| 99精品热视频| 久久久久久久激情视频| 亚洲一区二区三区在线播放| 久久一本综合频道| 欧美日韩中文另类| 极品日韩久久| av不卡在线看| 亚洲国产综合在线| 午夜精品久久久| 一本大道久久精品懂色aⅴ | 狠狠久久婷婷| 中国成人黄色视屏| 一本久久综合亚洲鲁鲁| 欧美一区午夜视频在线观看| 一区二区精品在线观看| 久久久综合激的五月天| 欧美一区二区三区啪啪| 欧美精品一区在线播放| 欧美二区在线播放| 国产主播一区| 亚洲永久网站| 亚洲欧美影院| 欧美视频官网| 亚洲精品久久久久久下一站 | 欧美激情a∨在线视频播放| 国产亚洲综合在线| 亚洲免费在线观看视频| 亚洲午夜电影| 国产精品v片在线观看不卡| 亚洲高清影视| 亚洲国产精品激情在线观看| 久久精品91| 久久综合一区| 亚洲大片av| 久久伊人亚洲| 女主播福利一区| 亚洲电影在线| 老司机免费视频一区二区三区| 麻豆久久久9性大片| 国产一区二区三区久久久| 亚洲欧美日韩一区二区在线| 亚洲欧美成人在线| 国产精品午夜电影| 亚洲神马久久| 欧美一区二区精品| 国产亚洲免费的视频看| 久久国产精品一区二区三区四区| 久久激情中文| 黄色亚洲在线| 欧美成人精品在线视频| 亚洲日本中文字幕| 国产精品99久久久久久有的能看| 欧美日韩久久不卡| 亚洲视频综合| 久久久www免费人成黑人精品| 好吊妞**欧美| 欧美黑人多人双交| 一区二区三区四区国产精品| 性久久久久久久久| 伊人男人综合视频网| 蜜桃久久精品一区二区| 亚洲精品久久久久久久久久久久| 亚洲一区二区视频在线| 国产日韩欧美在线观看| 久久全国免费视频| 亚洲美女少妇无套啪啪呻吟| 亚洲欧美日韩一区二区在线| 国产午夜精品一区理论片飘花| 久久亚洲图片| 一区二区三区国产在线| 久久久久久久久久久久久女国产乱| 亚洲欧美日韩国产一区二区三区 | 亚洲精品欧美极品| 欧美三级免费| 欧美一级免费视频| 亚洲欧洲精品一区二区三区不卡 | 亚洲精品免费网站| 欧美一级淫片aaaaaaa视频| 红桃视频一区| 欧美日韩在线播放| 欧美影片第一页| 亚洲精品一区久久久久久| 久久国产日韩| 中日韩美女免费视频网址在线观看 | 欧美精品v国产精品v日韩精品| av72成人在线| 欧美二区在线| 久久精品国产一区二区电影| 日韩视频三区| 极品少妇一区二区三区精品视频 | 久久不射2019中文字幕| 亚洲精品女av网站| 在线观看欧美一区| 国产麻豆综合| 国产精品草莓在线免费观看| 免费日韩av片| 久久九九免费视频| 亚洲欧美日韩另类精品一区二区三区| 亚洲激情不卡| 欧美成人精品在线播放| 欧美在线一级视频| 亚洲女女女同性video| 一本一本久久a久久精品牛牛影视| 影音先锋亚洲精品| 国产在线乱码一区二区三区| 国产精品国产三级国产专播精品人| 老司机精品福利视频| 久久久久国产精品www| 欧美伊久线香蕉线新在线| 亚洲一区二区三区777| 日韩视频中文| 亚洲美女视频在线观看| 亚洲人成人99网站| 欧美激情精品久久久久久蜜臀 | 欧美成黄导航| 老巨人导航500精品| 久久久99国产精品免费| 久久久精品网| 久久精品最新地址| 久久精品国产一区二区三区免费看| 性欧美大战久久久久久久免费观看| 亚洲午夜精品| 亚洲欧美在线另类| 性欧美xxxx大乳国产app| 性做久久久久久免费观看欧美 | 欧美在线观看视频一区二区三区| 一区二区三区日韩精品| 亚洲午夜久久久久久久久电影院| 久久久夜夜夜| 亚洲欧洲三级| 日韩午夜免费视频| 亚洲色无码播放| 亚洲资源av| 小辣椒精品导航| 久久久久久69| 免费美女久久99| 亚洲国产导航| 一区二区三区导航| 亚洲欧美在线一区二区| 欧美伊人影院| 免费成人高清视频| 欧美巨乳波霸| 国产精品日韩二区| 狠狠色综合网站久久久久久久| 在线免费观看日韩欧美| 亚洲免费久久| 午夜日韩在线| 欧美本精品男人aⅴ天堂| 亚洲精品韩国| 久久国产精品99精品国产|