接下來的章節會來討論minimum spanning tree的議題。

首先來了解一下什麼是spanning tree：

在一個graph G中，若有一個graph T滿足以下三個條件即為spanning tree：

1. 所有節點都相連
2. 不會有cyclic存在
3. 這個T包含了G所有的節點

而minimum spanning tree則是在所有可能的T中，其edge的weight總和最小者，即為MST(minimum spanning tree)。

有個有趣的問題，MST會等於graph的SPT(shortest path tree)嗎？我們可以試著分析看看：

由上圖可知，SPT的形成取決於起點在哪裡，上面的範例中若從點B來出發的話，確實MST等於SPT，但是不是每個graph的兩者都一樣。

那該如何找出graph中的MST呢？

在著手進行這項工程以前，首先要來介紹一個特性，叫做cut property：

cut：假設我們把graph中的節點分成兩群，這樣的情形就稱為cut。

crossing edge：當edge兩邊的節點是不同群時，就稱這個edge為crossing edge；如上圖中的紅色edge兩邊的節點是灰點和白點，這些紅edge都是crossing edge。

cut property：所有的crossing edge中weight最小的稱為minimum crossing edge，而該graph的MST一定會包含minimum crossing edge。

真的是這樣嗎？

要證明cut property其實滿容易的：

上圖中假設minimum crossing edge是e，我們找出MST但故意不包含e，此時這個MST一定也會包含到其他crossing edge，這邊假設是f。

又e肯定比f小，故真正的MST就肯定會包含minimum crossing edge，得證～

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License