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

            最新隨筆

            搜索

            最新評論

            獨立博客: 哲學與程序
            99久久精品免费看国产一区二区三区 | 久久九九兔免费精品6| 久久久久人妻精品一区三寸蜜桃| 93精91精品国产综合久久香蕉 | 人妻无码久久一区二区三区免费| 97久久超碰国产精品旧版| 青青草原1769久久免费播放| 久久激情亚洲精品无码?V| 久久天天躁狠狠躁夜夜2020一 | 久久精品国产亚洲av日韩| 国内精品久久久久久久久电影网| 亚洲欧美国产日韩综合久久| 老色鬼久久亚洲AV综合| 久久精品国产一区二区电影| 国产69精品久久久久9999APGF | 国产精品美女久久久久久2018| 精品久久人人妻人人做精品| 亚洲精品无码久久久久去q| 麻豆久久| 国产精品综合久久第一页| 国产亚洲精品自在久久| 狠狠色噜噜色狠狠狠综合久久| 91麻精品国产91久久久久| 狠狠久久亚洲欧美专区| 色综合久久久久无码专区| 久久婷婷色综合一区二区| 色欲综合久久躁天天躁| 久久国产成人午夜aⅴ影院| 久久99久久99小草精品免视看| 久久婷婷五月综合色高清| 亚洲综合日韩久久成人AV| 久久亚洲精品国产精品婷婷| 久久久久久毛片免费看| 久久久久国产一区二区| 久久精品国产只有精品66| 久久久久亚洲AV综合波多野结衣 | 国产偷久久久精品专区| 欧美日韩精品久久久免费观看| 伊人情人综合成人久久网小说| 久久久久久国产a免费观看不卡| 99久久精品免费|