JAVA—咖啡館

          ——歡迎訪問rogerfan的博客,常來《JAVA——咖啡館》坐坐,喝杯濃香的咖啡,彼此探討一下JAVA技術(shù),交流工作經(jīng)驗,分享JAVA帶來的快樂!本網(wǎng)站部分轉(zhuǎn)載文章,如果有版權(quán)問題請與我聯(lián)系。

          BlogJava 首頁 新隨筆 聯(lián)系 聚合 管理
            447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks

          公告

           

          Locations of visitors to this page
          點擊這里給我發(fā)消息 點擊這里給我發(fā)消息

          常用鏈接

          留言簿(17)

          隨筆分類(542)

          隨筆檔案(438)

          文章分類(182)

          文章檔案(142)

          新聞分類

          ※→ 【JAVA文檔】

          ※→ 【親人博客】

          ※→ 【休閑娛樂】

          ※→ 【友情鏈接】

          ※→ 【學(xué)習(xí)網(wǎng)站】

          ※→ 【服務(wù)網(wǎng)站】

          ※→ 【著名網(wǎng)站】

          ※→ 【阿里博客】

          最新隨筆

          搜索

          積分與排名

          最新評論

          閱讀排行榜

          評論排行榜

          圖中代權(quán)的最小樹的問題如下:


          如果N個城市之間(圖中的頂點)要修公路(圖中的邊)以使所有的城市聯(lián)通,求怎樣修可以使得公路的總長最小?
          以上問題中的N個城市之間可以用圖中的頂點表示,公路可以圖中的邊表示,公路的長度用邊長表示,公路是雙向的。問題就轉(zhuǎn)換為在有N個頂點中的雙向代權(quán)圖中求得一個最小樹。這里的代權(quán)指的邊的長度,這與以前的不代權(quán)的最小樹生成算法有很大的區(qū)別。


          算法描述如下:


              任選一個節(jié)點開始,將該節(jié)點標志為已訪問過的節(jié)點。也就是最小樹中的節(jié)點。并設(shè)置為當前節(jié)點。
              1 尋找此訪問節(jié)點的所有的鄰接頂點,將邊置入優(yōu)先隊列。鄰接頂點不考慮已標志為訪問的節(jié)點,因為它已在結(jié)果中。
              2 重復(fù) 步驟1 直到?jīng)]有新的邊被發(fā)現(xiàn)。此時在所有發(fā)現(xiàn)的邊中找到最小的邊,將其終點頂點標志為已訪問,放入最小樹中。并設(shè)置為當前節(jié)點
              3 重復(fù) 步驟 1,2,直到邊的隊列中沒有多余的邊,算法結(jié)束。

              注意:這里的優(yōu)先級隊列是個修正過的優(yōu)先級隊列,每次向該隊列中加入一條新邊時后,會檢查是否有與新邊終點相同的第二條邊的存在,如果有,則刪除邊長較大的邊。因為如果存在這樣的邊說明,有兩條從已訪問過節(jié)點到相同目標節(jié)點的路徑存在,如果這樣的話只用保留最小的那條邊即可。

          這里的圖采用Graph 圖-鄰接矩陣法 表示。



          算法實際上是作如下操作:


              先準備好一個優(yōu)先級隊列,里面以邊長為關(guān)鍵值存放邊,邊的起點表示已被訪問過的節(jié)點,而邊的終點表示未訪問的節(jié)點。將某節(jié)點標志為訪問過節(jié)點。開始算法。
              尋找該訪問過節(jié)點的所有邊,并記錄邊長,放入邊優(yōu)先級隊列中;
              找到所有從已訪問過的節(jié)點到未訪問節(jié)點的邊中的最小邊;
              將最小邊連接的頂點設(shè)置為訪問過,重復(fù)以上過程,直到所有節(jié)點都變成已訪問。

          主要的類如下:

              Edge:記載邊

              PriorityQ:修正后的優(yōu)先級隊列

              Vertex:頂點

              Gragh:圖

                  Gragh.mstw():最小樹生成算法

                  Gragh.main():提供簡單測試

          代碼如下:

           

          JAVA代碼

           

          posted on 2008-05-28 15:45 rogerfan 閱讀(419) 評論(0)  編輯  收藏 所屬分類: 【JAVA算法】
          主站蜘蛛池模板: 凭祥市| 海丰县| 安泽县| 临沂市| 凭祥市| 潜江市| 和顺县| 阳东县| 泽州县| 靖安县| 祁东县| 涟源市| 葵青区| 井陉县| 宁武县| 太仆寺旗| 彩票| 时尚| 天祝| 雅江县| 田阳县| 星子县| 克山县| 忻州市| 武宣县| 襄汾县| 兴义市| 休宁县| 麦盖提县| 大悟县| 巴林左旗| 台东县| 崇仁县| 仁布县| 贵溪市| 保康县| 黄平县| 额敏县| 永吉县| 望奎县| 泰和县|