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