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

lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

Kruskal算法

Posted on 2009-04-10 19:41 lzmagic 閱讀(4588) 評論(1)  編輯 收藏 引用 所屬分類: Algorithm
/**
 * KRUSKAL 最小生成樹算法 (Minimum Spanning Tree) 
 * 輸入:圖g;                 // 有向圖或者無向圖 
 * 輸出:(1)最小生成樹長sum; 
 *         (2)最小生成樹mst。
 * 結構: 圖g用頂點數n和邊集edges(優先隊列)表示,兩點是否連通用并查集實現。 
 * 算法:Kruskal算法  
 * 復雜度:O(|E|*log|E|)~O(|E|*log|V|) 
 
*/
 
#include 
<iostream>
#include 
<string>
#include 
<vector>
#include 
<deque>
#include 
<list>
#include 
<stack>
#include 
<queue>
#include 
<set>
#include 
<map>
#include 
<bitset>
#include 
<iterator>
#include 
<algorithm>
#include 
<numeric>
#include 
<functional>
#include 
<climits>
using namespace std;

struct Edge
{
    
int u, v, w;        // u、v:兩個頂點  w:權 
    Edge() { }
    Edge(
int u0, int v0, int w0):u(u0), v(v0), w(w0) { }
}
;

int n;                    // n : 頂點個數 
vector<Edge> edges;        // edges : 圖g的所有邊 
int sum;                // sum : 最小生成樹長 
vector<Edge> mst;        // mst : 最小生成樹(用邊集表示) 

class DisjSets
{
    vector
<int> s;
    
public:
        DisjSets(
int n) : s(n, -1{ };
        
int find (int x)
        
{
            
if (s[x] < 0return x;
            
else return s[x] = find(s[x]);   // 壓縮路徑。 
        }
;
        
void unionSets(int root1, int root2)
        
{
            
if (s[root1] > s[root2])    // 按個數求并(個數用負數表示)。 
            {
                s[root2] 
+= s[root1];
                s[root1] 
= root2;
            }

            
else
            
{
                s[root1] 
+= s[root2];
                s[root2] 
= root1;
            }

        }
;
}


bool Cmp(const Edge &lhs, const Edge &rhs)
{
    
return lhs.w > rhs.w;
}
 

bool Kruskal()
{
    DisjSets ds(n);
    make_heap(edges.begin(), edges.end(), Cmp);    
// 對邊集建堆。 
    int root1, root2;
    Edge e;
    
while (!edges.empty())    // 遍歷所有邊, 
    {
        e 
= edges.front(); pop_heap(edges.begin(), edges.end(), Cmp); edges.pop_back();// 從未選邊集中尋找最小權的邊e。 
        root1 = ds.find(e.u), root2 = ds.find(e.v);    // 獲取u、v所在的點集, 
        if (root1 != root2)                // 如果u、v不是同一個點集, 
        {
            sum 
+= e.w;                 // 調整最小生成樹長 
            mst.push_back(e);             // 把邊e放入最小生成樹mst中, 
            ds.unionSets(root1, root2);    // 合并兩點所在的點集。 
        }

        
if (mst.size() == n - 1return true// 如果選取邊個數為n - 1,成功。
    }

    
return false;  
}


int main()
{
    n 
= 7;
    edges.clear();
    edges.push_back(Edge(
012)); edges.push_back(Edge(024));  edges.push_back(Edge(031));
    edges.push_back(Edge(
133)); edges.push_back(Edge(1410));
     edges.push_back(Edge(
232)); edges.push_back(Edge(255));
     edges.push_back(Edge(
347)); edges.push_back(Edge(358)); edges.push_back(Edge(364));
     edges.push_back(Edge(
466));
     edges.push_back(Edge(
561));
     
     sum 
= 0;
     mst.clear();
     
if(Kruskal())
     
{
        cout 
<< sum << endl;
        
for (vector<Edge>::iterator it = mst.begin(); it != mst.end(); ++it)
            cout 
<< it-><< "->" << it-><< endl;
    }

    
else
    
{
        cout 
<< "Some vertex cann't be reached." << endl; 
    }

     
    system(
"pause");
    
return 0;
}

Feedback

# re: Kruskal算法  回復  更多評論   

2010-12-06 22:14 by mwxjm
這個程序是不是有個bug:
如果節點數量為1,邊數量為0
則應該是有生成樹的,但是kruskal函數返回結果為false吧
個人意見
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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| 精品成人a区在线观看| 99国产精品国产精品久久| 欧美国产免费| 欧美欧美全黄| 亚洲一区国产一区| 亚洲欧美日韩综合| 在线观看欧美日韩| 亚洲精品久久久久久久久久久久久 | 91久久极品少妇xxxxⅹ软件| 欧美精品电影| 亚洲综合大片69999| 久久高清免费观看| 日韩视频三区| 亚洲欧美久久久| 在线日韩电影| 在线视频精品一区| 韩国一区二区三区美女美女秀| 欧美激情成人在线| 国产精品卡一卡二卡三| 久久免费偷拍视频| 欧美理论在线播放| 久久久久久久久久久成人| 欧美第一黄网免费网站| 午夜精品在线看| 乱码第一页成人| 欧美呦呦网站| 欧美精品偷拍| 美女爽到呻吟久久久久| 男人的天堂亚洲在线| 亚洲国产精品一区二区尤物区| 久久综合网色—综合色88| 欧美成人精品在线播放| 欧美一区二区女人| 免费高清在线视频一区·| 小黄鸭精品aⅴ导航网站入口| 久久不射中文字幕| 99riav国产精品| 午夜精品久久久久久久99樱桃 | 久久久精品日韩欧美| 这里只有精品视频| 美女主播一区| 久久久999| 国产精品天天看| 99精品国产热久久91蜜凸| 亚洲高清视频中文字幕| 亚洲欧美日韩在线播放| 亚洲欧美国产va在线影院| 欧美freesex8一10精品| 久久精品中文字幕一区二区三区| 国产精品xxxxx| av成人国产| 在线一区二区三区做爰视频网站 | 99国产一区| 日韩亚洲精品视频| 欧美α欧美αv大片| 久久精品国产亚洲一区二区三区| 欧美性大战久久久久久久蜜臀| 欧美www在线| 国内精品美女在线观看| 亚洲视频免费| 宅男在线国产精品| 欧美精品免费在线观看| 欧美成人精品不卡视频在线观看 | 欧美大片在线看| 亚洲经典三级| 亚洲精品一区在线| 欧美激情2020午夜免费观看| 亚洲电影免费在线| 99精品黄色片免费大全| 欧美精品久久久久久久免费观看| 亚洲激情影院| 亚洲欧美国产精品桃花| 国产免费成人av| 久久精品免费| 亚洲大片精品永久免费| 一本色道久久88亚洲综合88| 欧美日韩免费高清一区色橹橹| 中国成人黄色视屏| 久久久久久久尹人综合网亚洲| 国内精品模特av私拍在线观看| 久久免费视频一区| 欧美激情一区二区三区在线视频| 亚洲美女av网站| 国产精品va在线| 欧美中文字幕| 亚洲福利在线视频| 亚洲一区二区av电影| 国产日韩精品视频一区| 美女精品在线观看| 日韩视频免费在线| 午夜精品一区二区三区在线播放| 国产日韩欧美精品综合| 久久精品国产综合| 亚洲国产欧美在线| 亚洲一区二区在线播放| 国产精品青草久久| 久久久噜噜噜久久中文字免| 亚洲精品日韩一| 久久久久国产免费免费| 亚洲最新在线| 国产伦精品一区二区| 久久午夜激情| 日韩性生活视频| 久久一区二区三区四区五区| 亚洲精品一区二区三区樱花| 国产精品青草久久久久福利99| 欧美一级午夜免费电影| 欧美激情一区二区三区在线| 亚洲影视中文字幕| 今天的高清视频免费播放成人 | 午夜电影亚洲| 亚洲激情黄色| 久久国产一区二区| 亚洲婷婷国产精品电影人久久| 影音先锋久久| 国产亚洲欧美中文| 国产精品高潮呻吟久久| 免费在线一区二区| 久久精选视频| 性欧美办公室18xxxxhd| 99精品视频免费观看视频| 欧美国产日本韩| 久久一区欧美| 久久久久久伊人| 亚洲欧美另类在线| 亚洲私拍自拍| 亚洲三级免费电影| 狠狠色丁香久久婷婷综合_中| 欧美日韩在线播| 免费成人av资源网| 午夜免费日韩视频| 一区二区三区日韩欧美精品| 一区二区在线不卡| 国产欧美在线观看一区| 欧美日韩免费网站| 欧美福利视频网站| 久久精品免费电影| 欧美一区二区三区免费看| 亚洲一级在线观看| 日韩亚洲欧美高清| 亚洲国产日韩欧美在线99| 麻豆精品一区二区av白丝在线| 欧美亚洲在线播放| 欧美亚洲视频在线观看| 欧美一区二区在线看| 午夜精品一区二区在线观看| 亚洲香蕉在线观看| 亚洲一区二区视频在线观看| 日韩写真在线| 亚洲一区在线观看视频| 欧美一区二区高清在线观看| 欧美在线三级| 久久久欧美精品sm网站| 久久夜色精品国产亚洲aⅴ| 老鸭窝毛片一区二区三区 | 伊人久久婷婷| 1024成人| 91久久精品www人人做人人爽 | 欧美成人精品在线观看| 欧美国产日韩一区二区| 欧美国产激情| 欧美极品aⅴ影院| 国产精品videossex久久发布| 国产精品一区二区视频| 精久久久久久| 国产精品99久久久久久久久久久久 | 久久男人资源视频| 欧美日韩国产电影| 国产视频久久网| 在线观看欧美| 亚洲欧美精品在线观看| 久久久久免费观看| 亚洲日韩成人| 久久aⅴ乱码一区二区三区| 免费成人高清在线视频| 国产精品社区| 亚洲人午夜精品免费| 亚洲欧美在线观看| 欧美成人伊人久久综合网| 亚洲视频播放| 美女图片一区二区| 国产精品入口福利| 日韩亚洲欧美中文三级| 欧美一区二区在线免费观看| 欧美激情欧美激情在线五月| 亚洲在线成人| 欧美日韩一本到| 亚洲黄色三级| 久久久亚洲影院你懂的| 一本久久综合| 免费欧美视频| 黄色一区二区在线观看| 亚洲欧美一区二区原创| 亚洲国产一区二区a毛片| 欧美专区福利在线| 国产精品亚洲欧美| 在线亚洲免费视频| 亚洲国产精品久久久久秋霞不卡 | 国产欧美日本一区视频|