给定无向图G=(V,E)，连接G中所有点，且边集是E的n-1条边构成的无向连通子图称为G的生成树(Spanning Tree)，而边权值总和最小的生成树称为最小生成树（Minimal Spanning Tree,MST）。
