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

            Just enjoy programming

            最小生成樹

            安全邊:在每一次迭代之前, A是某個最小生成樹的一個子集。在算法的每一步中,確定一條邊(u,v),使得將它加入集合A后,仍然不違反這個循環不等式,A U {(u,v)}仍然是某一個最小生成樹的子集。稱這樣的邊為A的安全邊。

            識別安全邊的定理:設圖G=(V,E)是一個無向連通圖,并且在E上定義了一個具有實數值的加權函數w.設A是E的一個子集,它包含于G的某個最小生成樹中。設割(S,V-S)是G的任意一個不妨害A的割,且邊(u,v)是通過割(S,V-S)的一條輕邊,則邊(u,v)對集合A來說是安全的。


            推論:設G=(V,E)是一個無向聯通圖,并且在E上定義了相應的實數值加權函數w.設A是E的子集,并包含于G的某一最小生成樹中。設C=(Vc,Ec)為森林GA=(V,A) 的一個連通分支。如果邊是連接C和Ga中其他某聯通分支的一條輕邊,則(u,v)對集合A來說是安全.

            在Kruskal(克魯斯卡爾)算法和Prim(普里姆)算法
            在Kruskal算法中,集合A是一個森林,加入集合A中的安全邊總是圖中連接兩個不同聯通分支的最小權邊。在Prim算法中,集合A僅形成單棵樹,添加入集合A的安全邊總是連接樹與一個不在樹中的頂點的最小權邊。

            Kruskal(克魯斯卡爾)算法(O(ElgE)):
            該算法找出森林中連接任意兩棵樹的所有邊中,具有最小權值的邊(u,v)作為安全邊,并把它添加到正在生長的森林中。設C1和C2表示邊(u,v)連接的兩棵樹,因為(u,v)必是連接C1和其他某棵樹的一條輕邊,所以由上面推論可知,(u,v)對C1來說是安全邊。Kruskal 算法同時也是一種貪心算法, 因為在算法的每一步中,添加到森林中的邊的權值都是盡可能小的。
            下面是偽代碼:
            MST-KRUSKAL(G,w)
            A<--空集
            for each vertex v 屬于 V[G]
                  do MAKE-SET(v)
            sort the edges of E into nondecreasing order by weight w
            for each edge(u,v)屬于E,taken in nondecreasing order by weight
               do if FIND-SET(u)!=FIND-SET(v)
                        then  A<--AU{(u,v)}
                                 UNION(u,v)
            return A

            FIND-SET(u)返回包含u的集合中的一個代表元素。于是通過測試FIND-SET(u)是否等同于FIND-SET(v),就可以確定頂點u和v是否屬于同一棵樹。通過過程UNION,可以實現樹與樹的合并。


            Prim算法(O(ElgV))
                Prim算法的特點是集合A中的邊總是形成單棵樹。樹從任意根頂點r開始形成,并逐漸生成,直至該樹覆蓋了V中的所有頂點。在每一步,一條連接了樹A與Ga=(V,A)中某孤立頂點的輕邊被加入樹A中。由推論可知,該規則僅加入對A安全的邊,因此當算法終止時,A中的邊形成了一棵最小生成樹。因此每次添加到樹中的邊都是使樹的權盡可能小的邊,因此,上述策略也是“貪心“的。

            偽代碼如下:
            MST-PRIM(G,w,r)

            for each u 屬于V[G]
                        do key[u]  <--空集
                              n[u]<--NIL

            key[r]<--0
            Q<--V[G]
            while  Q!=空集
                do u<---EXTRACT-MIN(Q)
                     for each v屬于Adj[u]
                           do if v 屬于Q  and w(u,v)<key[v]
                                 then n[u]<---u
                                        key[v]<--w(u,v)


            參考:算法導論

            posted on 2011-05-19 11:09 周強 閱讀(677) 評論(2)  編輯 收藏 引用 所屬分類: 算法

            評論

            # re: 最小生成樹 2011-05-25 20:49 十三

            我有打算看算法導論呢~~
            機械工業出版社那本是吧~~  回復  更多評論   

            # re: 最小生成樹 2011-05-25 23:24 周強

            @十三
            恩,就是這本書。  回復  更多評論   

            久久久久女人精品毛片| 中文字幕无码精品亚洲资源网久久| 欧美va久久久噜噜噜久久| 日韩精品无码久久久久久| 久久精品国产秦先生| 国产午夜精品久久久久九九| 亚洲Av无码国产情品久久| 久久狠狠高潮亚洲精品| 人妻无码αv中文字幕久久| 国产成人久久激情91| 中文字幕亚洲综合久久菠萝蜜| 俺来也俺去啦久久综合网| 欧美久久一级内射wwwwww.| 欧洲精品久久久av无码电影| 久久国产免费| 久久美女人爽女人爽| 香蕉久久夜色精品升级完成| 久久久久亚洲AV无码去区首| 97久久久精品综合88久久| 国产精品久久久久久久久软件| 久久精品国产一区| 国内精品伊人久久久久av一坑| 性做久久久久久久久久久| 久久这里只有精品久久| 久久久精品国产sm调教网站| 久久人人添人人爽添人人片牛牛| 狠狠色伊人久久精品综合网| 91久久精一区二区三区大全| 色88久久久久高潮综合影院| 久久婷婷五月综合97色直播| 久久嫩草影院免费看夜色| 国产精品激情综合久久| 欧美久久精品一级c片片| 久久国产乱子精品免费女| 亚洲狠狠婷婷综合久久蜜芽| 2020久久精品亚洲热综合一本| 久久人人爽人人爽人人片AV东京热| 国产亚洲美女精品久久久| 麻豆精品久久久一区二区| 999久久久国产精品| 久久国产精品波多野结衣AV|