最小生成树

一．问题描述

构造一无向连通网，用Prim算法或Kruskal算法实现最小生成树的算法

二．实验目的

1．掌握网的基本概念和连通网的存储结构

2．掌握最小生成树的算法实现

三．实验要求

1．确定边的相邻顶点和权植，建立无向连通网，实现最小生成树。

2．Prim算法思想：

设G=（V，E）是一个无向连通图，令T=（U，TE）是G的最小生成树。T的初始状态为U={v0}，TE={}，然后重复执行下述操作：在所有u，v的边中找一条代价最小的边（u，v）并入集合TE，同时v并入U，直至U=V为止。此时TE中必有n-1条边，T就是最小生成树。