最小生成树

最小生成树是一副连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 中， 代表連接頂點 u 與頂點 v 的邊（即 ），而 代表此邊的權重，若存在 T 為 E 的子集（即 ）且 (V, T) 為樹，使得 的 w(T) 最小，則此 T 為 G 的最小生成樹。 最小生成樹其實是最小權重生成樹的簡稱。 一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。 以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。