最小樹圖是在有向賦權圖中指定壹個特殊點V，求壹棵有向生成樹T，使有向樹的根為V，T中所有邊的總權最小。
判斷是否有樹圖的方法很簡單，只需要以V為根遍歷壹次圖即可。所以下面的算法不再考慮樹圖不存在的情況，我們需要在所有操作開始之前清除圖中所有的自環。
首先，為每個點選擇壹條邊，根除外，它必須是所有邊中最小的壹條。所有最小的邊都被選中。如果這個邊集中沒有有向圈，我們可以證明這個集是圖的最小樹圖。
如果有壹個有向環，我們應該稱之為人工頂點，改變圖中邊的權重。假設環上有某個點U，環上指向U的邊權在[u]中，那麽對於從U開始的每條邊(U，I，w)，在新的圖中連接(new，I，w)的邊，其中new是新增加的人工頂點；對於進入u的每個邊(I，u，w ),
在新圖形中創建邊(I，new，w-in[u])的邊。為什麽in[u]應該從邊的重量中減去？這個後面會解釋，這裏先給出算法的步驟。可以證明新圖中最小樹圖的權加上舊圖中收縮環的權和就是原圖中最小樹圖的權。
如果E在新圖中的權重w'(e)是E在原圖中的權重w(e)減去在[u]中的權重，那麽當我們刪除in[u]並將E恢復到原圖時，這個樹圖的權重仍然是新圖的樹圖的權重加環，這個權重就是最小樹圖的權重。
所以每次收縮的復雜度是O(E)，然後最多會收縮多少次？由於我們已經去掉了開頭的所有自環，所以我們可以知道每個環至少包含2個點。縮小成1分後，總點數至少減少1。當整個圖縮減到只有1個點時，最小樹圖就沒有必要了。
所以我們最多只會收縮V-1倍，所以總復雜度自然是O(VE)。因此，如果壹開始不去除自環，理論復雜度將與自環的數目有關。