mst(最小生成樹(minimum spanning tree))

一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，並且有保持圖連通的最少的邊。 最小生成樹可以用kruskal（克魯斯卡爾）算法或prim（普里姆）算法求出。

基本介紹

• 中文名：最小生成樹
• 外文名：Minimum Spanning Tree,MST

術語解釋

最小生成樹性質：設G=(V，E）是一個連通網路，U是頂點集V的一個非空真子集。若(u，v）是G中一條“一個端點在U中（例如：u∈U），另一個端點不在U中的邊（例如：v∈V-U），且（u，v）具有最小權值，則一定存在G的一棵最小生成樹包括此邊（u，v）。