熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之最小生成樹

2013-11-15 15:33:12  來源: 數據結構 

最小生成樹的概念和應用背景

  最小生成樹(Minimum Spanning Tree)各邊權的總和最小的生成樹
  MST性質
  假設N=(VE)是一個連通網U是頂點集V的一個非空子集若(UV)是一條具有最小權值的邊其中u∈Uv∈VU則必存在一棵包含邊(UV)的最小生成樹

構造最小生成樹的常用算法

  普裡姆(Prim)算法
  基本思想設G=(VE)是連通網頂點集V={vvvn}T=(UTE)是欲構造的最小生成樹任選V中一頂點(不妨為v初始化U={v}TE=Φ重復下列操作在所有u∈U中v∈VU的邊(uv)∈E中選擇一條權值最小的邊(uv)並入TE同時將v並入U直到U=V為止這時產生的TE中具有n條邊則上述過程求得的T=(UTE)是G的一棵最小生成樹
  普裡姆算法的時間復雜度為O(n)與圖中邊數無關該算法適合於稠密圖
  克魯斯卡爾(Kruskal)算法
  基本思想設T是無向連通網G的最小生成樹E(T)是其邊集則令最小生成樹的初始狀態為n個頂點而無邊的非連通圖即E(T)為空集圖中每個頂點自成一個連通分量在E中選擇權值最小的邊若該邊依附的頂點落在T中不同的連通分量上則將此邊加入到T中否則捨去此邊而選擇下一條權值最小的邊依次類推直至T中所有頂點都在同一連通分量上為止(此時已選中n條邊)
  克魯斯卡爾算法的時間復雜度為O(elge)時間主要取決於邊數較適合於稀疏圖


From:http://tw.wingwit.com/Article/program/sjjg/201311/23588.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.