最小樹形圖算法

介紹

最小樹形圖算法(minimum arborescence algo- rithm)一種求圖上有向樹的方法.它的基本思想 是:任給有向網路G，先對每一點選一條權最小的入 弧，再從這n條弧中選n-1條權較小的弧，然後觀 察由這n-1條弧所構成的G的支撐子圖是否包含 有向圈.若含有有向圈，則通過收縮有向圈得到一個 新的網路.這網路的弧數與點數總比原來的少.對這 新網路再繼續上面的方法，於是便得到一個網路的 遞減序列:}0}}1 } }}} }}k.這時，要么Vk不具有支撐 樹形圖，從而G也不具有支撐樹形圖;要么Vk有一 個最小樹形圖.因此，可按}k}...}}j}f}。的順序逐步 展開，便得到一個最小樹形圖的序列Hk}...}H}f 月。.月(。是G的最小樹形圖.