• <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>

            yuanyuelang

            常用鏈接

            統(tǒng)計

            最新評論

            不相交集合數(shù)據(jù)結(jié)構(gòu)

            不相交集合數(shù)據(jù)結(jié)構(gòu)保持一組不相交的動態(tài)集合s={s1,s2,...},每個集合通過一個代表來識別,代表是集合中的某個元素。

            不相交集合的應(yīng)用較為經(jīng)典的是判斷會不會構(gòu)成連通圖,用于最小生成樹的Kruskal算法。

            基本操作有:
            make_set(x):建立一個新的集合,其唯一成員也就是代表為X。代表X都不同,起初各個集合肯定是不相交的。

            union(x,y):將包含x,y元素的集合合并為一個新的集合,此時要選出一個新的代表來代表這個集合,并且將原先的包含x,y元素的集合刪除掉,將新集合加入到S中

            find_set(x):返回包含x元素的集合的那個代表。

            綜上所述,如何來選擇新集合的代表和find_set(x)將是我們要考慮到周密的問題。

            接下來我們介紹按秩合并和路徑壓縮啟發(fā)式的方法來解決這個問題

            看代碼分析吧:

            #define N 1000
            int p[N],rank[N];
            void make_set(int x)
            {
              p[x]
            =x;
              rank[x]
            =0;
            }

            void union(int x,int 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]
            ++;
              }
            }

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


            建議讀者好好幾個例子來分析下咯。。。














            posted on 2009-09-13 20:48 原語餓狼 閱讀(1057) 評論(1)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)

            評論

            # re: 不相交集合數(shù)據(jù)結(jié)構(gòu)[未登錄] 2010-02-09 19:19 a

            太簡陋了一點吧  回復(fù)  更多評論   


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            久久夜色撩人精品国产| 亚洲精品国产自在久久| 久久99精品久久久久久hb无码 | 久久久精品日本一区二区三区| 久久精品国产亚洲网站| 狠狠色综合久久久久尤物| 久久久久人妻一区二区三区| 久久婷婷久久一区二区三区| 中文字幕精品无码久久久久久3D日动漫| 超级碰碰碰碰97久久久久| 成人免费网站久久久| 亚洲熟妇无码另类久久久| 99久久人人爽亚洲精品美女| 久久精品国产亚洲AV蜜臀色欲| 久久艹国产| 久久亚洲欧美日本精品| 亚洲精品白浆高清久久久久久| 久久精品国产WWW456C0M| 精品国产VA久久久久久久冰| 99久久精品国产一区二区| 久久av免费天堂小草播放| 国产一区二区三区久久精品| 无码人妻久久一区二区三区免费丨 | 亚洲精品WWW久久久久久| 久久国产午夜精品一区二区三区| 亚洲国产精品无码久久一区二区| 久久一区二区三区免费| 久久亚洲国产精品一区二区| 国产精品女同久久久久电影院| 午夜人妻久久久久久久久| 日本WV一本一道久久香蕉| 少妇无套内谢久久久久| 青青热久久国产久精品| 人妻中文久久久久| 一本色综合久久| 久久毛片一区二区| 久久久久99这里有精品10 | 99久久综合国产精品免费| 久久久久久久久久久精品尤物 | 久久99毛片免费观看不卡 | 国产亚洲精品自在久久|