Prim最小生成树算法实验报告 算法分析与设计之 Prim 学院：软件学院 学号：202121031059 姓名：吕吕 一、 问题描述 1. m Prim 的定义 Prim 算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。 2. 实验目的 选择一门编程语言，根据 Prim 算法实现最小生成树，并打印最小生成树权值。 二、 算法分析与设计 m 1.Prim 算法的实现过程 基本思想：假设 G(V，E)是连通的，TE 是 G 上最小生成树中边的集合。算法从 Uu0（u0V）、TE开始。重复执行下列操作： 在所有 uU，vVU 的边(u，v)E 中找一条权值最小的边(u0,v0)并入集合 TE 中，同时 v0 并入 U，直到 VU 为止。 此时，TE 中必有 n-1 条边，T=(V，TE)为 G 的最小生成树。 Prim 算法的核心:始终保持 TE 中的边集构成一棵生成树。 2
