圖說演算法使用JavaScript(三十五)

10-4 擴張術的密碼

擴張樹又稱(花費樹)或(植樹)，一個圖形的擴張樹(Spanning Tree)就是以最少的編來連結圖形中所有的頂點，且不造成循環(Cycle)的樹狀結構。假設在樹的編加上一個權重(weight)值，這種圖形就成為(加權圖形 Weighted Graph)。如果這個權重值代表兩個頂點間的距離(distance)或成本(Cost)，這類圖形就稱為網路(Network)。如下圖所示：