• <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>
            獨立博客: 哲學與程序

            哲學與程序

            最小樹形圖

            何謂最小樹形圖,最小樹形圖,在一個有向圖中,定義某個節點為根節點,由該根節點擴展出來的一顆有向的生成樹,并且使這棵樹的權值最小。練習題POJ3164
            解決該問題的算法有兩位中國人提出,有位同學將該論文總結一下:
            最小樹形圖算法(Zhu-Liu Algorithm):

            1.  設最小樹形圖的總權值為cost,置cost為0。

            2.  除源點外,為其他所有節點Vi找一條權值最小的入邊,加入集合T。T就是最短邊的集合。加邊的方法:遍歷所有點到Vi的邊中權值最小的加入集合T,記pre[Vi]為該邊的起點,mincost[Vi]為該邊的權值。

            3.  檢查集合T中的邊是否存在有向環,有則轉到步驟4,無則轉到步驟5。這里需要利用pre數組,枚舉檢查過的點作為搜索的起點,類似dfs的操作判斷有向環。

            4.  將有向環縮成一個點。設環中有點{Vk1,Vk2,…,Vki}共i個點,用Vk代替縮成的點。在壓縮后的圖中,更新所有不在環中的點V到Vk的距離:

            map[V][Vk] = min {map[V][Vkj]-mincost[Vki]} 1<=j<=i;

            map[Vk][V] = min {map[Vkj][V]}           1<=j<=I

            5.  cost加上T中有向邊的權值總和就是最小樹形圖的權值總和。

            posted on 2011-05-26 13:22 哲學與程序 閱讀(758) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm

            導航

            公告

            歡迎訪問 http://zhexue.sinaapp.com

            常用鏈接

            隨筆分類(37)

            隨筆檔案(41)

            Algorithm

            最新隨筆

            搜索

            最新評論

            獨立博客: 哲學與程序
            久久伊人五月丁香狠狠色| 亚洲va中文字幕无码久久不卡| 久久99精品久久久久子伦| a高清免费毛片久久| 99久久精品国产一区二区| 伊人久久大香线蕉影院95| 久久综合久久鬼色| 日韩乱码人妻无码中文字幕久久| 久久精品www人人爽人人| 久久精品成人一区二区三区| 久久精品国产亚洲av麻豆图片| 久久99热狠狠色精品一区| 久久综合色老色| 久久91精品国产91| 国产一区二区三区久久| 中文字幕乱码人妻无码久久| 国产精品综合久久第一页 | 九九精品99久久久香蕉| 久久久久久极精品久久久| 久久久久国产精品嫩草影院| 丁香久久婷婷国产午夜视频| 无码人妻久久一区二区三区免费丨| 999久久久免费国产精品播放| 久久婷婷五月综合国产尤物app | 久久久久久久波多野结衣高潮| 欧美精品一本久久男人的天堂| 亚洲精品无码久久久久sm| 亚洲国产综合久久天堂| 国内精品久久久久久久亚洲 | 久久99精品久久久久久久久久| 亚洲精品国产第一综合99久久| 国产三级观看久久| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 99蜜桃臀久久久欧美精品网站| 国产精品免费久久久久久久久| 久久99国产亚洲高清观看首页 | 国产农村妇女毛片精品久久| 国产精品久久国产精品99盘| 久久久久亚洲AV片无码下载蜜桃| 人妻无码中文久久久久专区| 亚洲午夜久久久影院|