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

yuanyuelang

常用鏈接

統(tǒng)計(jì)

最新評(píng)論

最小生成樹之Kruskal算法

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

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

我們先來介紹Kruskal算法,Prim算法請(qǐng)參閱最小生成樹之Prim算法

該算法的基本思路:貪心,如何貪心呢?
它的貪心準(zhǔn)則是:
1.每次從剩下的邊中選擇一個(gè)不會(huì)產(chǎn)生環(huán)路而且權(quán)值最小的邊加入到已經(jīng)選擇好的邊的集合中。
2.它需要e步的操作,e表示圖的邊數(shù),我們可以按權(quán)值排好序后,對(duì)每一條邊進(jìn)行選擇,如果加入到已經(jīng)選擇好的邊中會(huì)產(chǎn)生回路的現(xiàn)象,就不要了。。。否則加入到已經(jīng)選擇好的邊中。
3.我們還需用到并查集的思想,有關(guān)并查集的介紹,請(qǐng)查看我的另一篇博文 不相交集合數(shù)據(jù)結(jié)構(gòu)
4.復(fù)雜度:O(ElgE),其中E為圖的邊數(shù)

接下來我們引用POJ上的一個(gè)經(jīng)典題目來分析,題目網(wǎng)址http://acm.pku.edu.cn/JudgeOnline/problem?id=1861

題目大意是:題目給出的是圖的頂點(diǎn)和所有邊的集合,要求輸出的是最小生成樹的邊

我們來看下源碼啦:
#include<iostream>
using namespace std;
#include
<algorithm>
#include 
<memory.h>

#define MAXEDGE 15001//最大邊數(shù)
#define MAXNODE 1001 //最大節(jié)點(diǎn)數(shù)

int p[MAXNODE],rank[MAXNODE];//用于不相交集合
int start[MAXEDGE],end[MAXEDGE],weight[MAXEDGE],VNum,ENum;//分別為邊的起點(diǎn),終點(diǎn),權(quán)重,節(jié)點(diǎn)數(shù)和邊數(shù)
int result_s[MAXEDGE],result_e[MAXEDGE];//分別為存儲(chǔ)最小生成樹的起點(diǎn),終點(diǎn)
int max_weight,id[MAXEDGE];

void make_set(int x)
{
    p[x]
=x;
    rank[x]
=0;
}


int find_set(int x)

    
if(p[x]!=x)
        p[x]
=find_set(p[x]);
    
return p[x];
}


void Union(int x,int y)
{
    x
=find_set(x);
    y
=find_set(y);
    
if(rank[x]>rank[y])
        p[y]
=x;
    
else if(rank[x]<rank[y])
        p[x]
=y;
    
else if(rank[x]==rank[y])
    
{
        p[x]
=y;
        rank[y]
++;
    }

}


bool cmp(int i,int j)//用于sort函數(shù)
{
    
return weight[i]<weight[j];
}

void Kruskal()
{
    
int i,min,index=0,count=0,k=0;
    
    max_weight
=0;
        
for(i=1;i<=VNum;i++)
          make_set(i);
    
        sort(id,id
+ENum,cmp);//對(duì)所有邊進(jìn)行排序,注意id數(shù)組的妙用
    while(true){
      min
=id[index++];
      
if(find_set(start[min])!=find_set(end[min]))//對(duì)每條邊進(jìn)行處理,如果起點(diǎn)和終點(diǎn)不在同一集合合并之
        Union(start[min],end[min]);
        result_s[k]
=start[min];//保存結(jié)果
                result_e[k++]=end[min];
                count
++;
        
if(max_weight<weight[min])
                max_weight
=weight[min];
       }

      
        
if(count==VNum-1break;//當(dāng)邊數(shù)等于節(jié)點(diǎn)數(shù)-1的時(shí)候表示已經(jīng)完成
    }

}






int main()
{
    
int i;
    cin
>>VNum>>ENum;
    
for(i=0;i<ENum;i++){
        cin
>>start[i]>>end[i]>>weight[i];
        id[i]
=i;
    }

        Kruskal();
        cout
<<max_weight<<endl<<VNum-1<<endl;
        
for(i=0;i<VNum-1;i++)
       cout
<<result_s[i]<<" "<<result_e[i]<<endl;
   
        
return 0;
}


posted on 2009-09-13 21:18 原語餓狼 閱讀(712) 評(píng)論(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香蕉国产| 国产婷婷一区二区| 亚洲国产精品久久久久秋霞影院| 亚洲观看高清完整版在线观看| 欧美国产精品中文字幕| 久久精品亚洲乱码伦伦中文| 欧美一区二区三区四区高清| 亚洲欧美国产日韩中文字幕| 亚洲欧美日韩国产成人| 亚洲欧洲日本专区| 国产精品99久久久久久www| 亚洲一区在线看| 久久久久久高潮国产精品视| 麻豆视频一区二区| 欧美日韩国产一区二区三区地区| 欧美视频你懂的| 韩日欧美一区| 中日韩男男gay无套| 午夜精品久久99蜜桃的功能介绍| 久久久国产成人精品| 亚洲人成77777在线观看网| 亚洲欧美一区在线| 欧美激情四色| 亚洲高清视频中文字幕| 一区二区三区精密机械公司 | 欧美福利精品| 国产精品高潮久久| 99re8这里有精品热视频免费| 亚洲欧美一区二区三区久久| 欧美一级专区免费大片| 日韩视频专区| 欧美激情导航| 亚洲视频网在线直播| 夜夜夜精品看看| 国产精品久久久久久久免费软件 | 一本色道久久综合狠狠躁篇的优点 | 欧美成人国产一区二区| 伊人天天综合| 欧美激情第3页| 欧美日韩另类国产亚洲欧美一级| 亚洲免费观看视频| 一本色道88久久加勒比精品| 国产精品亚洲片夜色在线| 欧美在线你懂的| aa成人免费视频| 日韩一区二区久久| 国产日韩欧美自拍| 欧美插天视频在线播放| 欧美日韩国产电影| 久久久久久999| 欧美激情综合网| 性欧美xxxx视频在线观看| 欧美一级专区| 亚洲欧美日韩一区在线| 久久久亚洲国产天美传媒修理工| 亚洲精品自在久久| 久久大逼视频| 久久久久国产成人精品亚洲午夜| 欧美韩国日本一区| 欧美成年人网| 亚洲丰满少妇videoshd| 欧美一区永久视频免费观看| 亚洲另类在线视频| 免费中文日韩| 欧美11—12娇小xxxx| 极品裸体白嫩激情啪啪国产精品| 亚洲深夜福利在线| 99视频精品免费观看| 欧美在线一级视频| 久久亚洲综合| 黄色成人精品网站| 久久人人九九| 欧美激情第三页| 99re这里只有精品6| 欧美理论片在线观看| 亚洲理伦在线| 久久香蕉国产线看观看av| 国产一区二区看久久| 久久精品国产视频| 欧美福利电影在线观看| 最新成人av网站| 欧美精品首页| 欧美亚洲自偷自偷| 久久人人爽人人爽| 一区二区三区在线高清| 久久夜色精品国产| 亚洲伦理在线| 久久亚洲综合网| 亚洲无线视频| 亚洲第一毛片| 国产日韩一区二区| 欧美视频在线视频| 久久精品成人一区二区三区 | 一本大道久久a久久精品综合| 欧美日韩国产影院| 久久亚洲美女| 欧美一区二区三区另类| 亚洲国产欧美一区| 久久一二三国产| 欧美一区二区久久久| 一本一本大道香蕉久在线精品| 国产精品免费看久久久香蕉| 毛片精品免费在线观看| 亚洲尤物在线| 羞羞视频在线观看欧美| 一区二区三区四区精品| 一区二区三区**美女毛片| 亚洲黄色一区| 亚洲区一区二| 亚洲精品欧美| 一区二区在线观看视频在线观看| 欧美福利视频在线| 欧美成人精品在线播放| 亚洲精品一二| 久久手机免费观看| 久久亚洲美女| 欧美mv日韩mv国产网站| 免费不卡在线观看| 国产美女搞久久| 国产精品永久免费视频| 国产一区 二区 三区一级| 国内精品美女在线观看| 国模精品一区二区三区色天香| 黄色成人av| 亚洲小视频在线观看| 欧美尤物巨大精品爽| 欧美不卡视频一区| 99国产精品视频免费观看| 亚洲主播在线| 欧美国产丝袜视频| 国产精品青草综合久久久久99| 国产亚洲亚洲| 99re66热这里只有精品4| 欧美中文字幕在线视频| 亚洲精品欧美在线| 美女主播精品视频一二三四| 国产精品久久777777毛茸茸| 亚洲第一搞黄网站| 久久青青草综合| 午夜精品福利在线观看| 欧美午夜在线视频| 亚洲视频中文字幕| 最新高清无码专区| 免费成人在线视频网站| 激情成人中文字幕| 免费在线亚洲| 开心色5月久久精品| 亚洲成人影音| 亚洲欧美日韩综合国产aⅴ| 亚洲激情国产| 欧美人成网站| 亚洲在线视频网站| 亚洲午夜在线| 国产午夜精品在线| 鲁大师影院一区二区三区| 快播亚洲色图| 亚洲一品av免费观看| 亚洲香蕉网站| 伊人久久婷婷色综合98网| 牛夜精品久久久久久久99黑人| 欧美成人一区二免费视频软件| 亚洲精品在线观看免费| 欧美视频一区二区三区在线观看| 欧美激情中文字幕一区二区| 一本久久综合亚洲鲁鲁| 亚洲欧美日韩在线| 亚洲激情一区二区| 亚洲一区视频| 亚洲免费电影在线观看| 亚洲欧美一区二区在线观看| 亚洲国产精品一区二区第四页av| 亚洲欧洲日夜超级视频| 国产亚洲精品美女| 亚洲精品一区在线观看香蕉| 黑人中文字幕一区二区三区 | 性欧美超级视频| 久久久久久久久久久久久久一区| 日韩一级免费| 欧美激情在线| 亚洲第一久久影院| 曰本成人黄色| 久久久国产成人精品| 久久久精品久久久久| 国产精品久久激情| 亚洲激情综合| 日韩视频不卡| 欧美日韩一区免费| 亚洲经典三级| 国产精品99久久不卡二区| 欧美经典一区二区三区| 亚洲第一页中文字幕| 91久久国产自产拍夜夜嗨| 免费亚洲电影| 99re热这里只有精品免费视频| 在线亚洲精品| 欧美午夜精品理论片a级大开眼界| 亚洲精品美女在线观看| 一区二区三区鲁丝不卡| 欧美精品自拍| 香蕉久久a毛片|