实验3 贪心算法（定稿）_实验三贪心算法

实验3 贪心算法（定稿）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“实验三贪心算法”。

《算法设计与分析》实验报告

实验3贪心算法

姓名 学号班级 实验日期实验地点

一、实验目的1、掌握贪心算法的设计思想。

2、理解最小生成树的相关概念。

二、实验环境

1、硬件环境 CPU：酷睿i5 内存：4GB 硬盘：1T2、软件环境

操作系统：Windows10 编程环境：jdk 编程语言：Java

三、实验内容：在Prim算法与Kruskal算法中任选一种求解最小生成树问题。

1、你选择的是：Prim算法

2、数据结构

（1）图的数据结构——图结构是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系，即结点之间的关系可以是任意的，图中任意元素之间都可能相关。

图形结构——多个对多个，如

（2）树的数据结构——树结构是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。树形结构——一个对多个，如

3、算法伪代码 Prim(G,E,W)输入：连通图G 输出：G的最小生成树T 1.S←{1};T=∅ 2.While V-S ≠∅ do

3.从V-S中选择j使得j到S中顶点的边e的权最小；T←T∪{e} 4.S←S∪{j}

3、算法分析 时间复杂度：O(n)空间复杂度：O(n^2)

4、关键代码（含注释）

package Prim;

import java.util.*;publiccla Main { staticintMAXCOST=Integer.MAX_VALUE;

staticint Prim(intgraph[][], intn){ /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */

intlowcost[]=newint[n+1];

/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */ intmst[]=newint[n+1];

intmin, minid, sum = 0;

/* 默认选择1号节点加入生成树，从2号节点开始初始化 */ for(inti = 2;i

/* 标记1号节点加入生成树 */ mst[1] = 0;

/* n个节点至少需要n-1条边构成最小生成树 */ for(inti = 2;i

/* 找满足条件的最小权值边的节点minid */ for(intj = 2;j

/* 输出生成树边的信息:起点，终点，权值 */

System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j

5、实验结果（1）输入

（2）输出

最小生成树的权值为： 生成过程：

(a)

(b)

(d)

(e)

(c)

四、实验总结（心得体会、需要注意的问题等）

这次实验，使我受益匪浅。这次实验我选择了Prim算法来求出树的最小生成树，在编写代码的过程中，我对Prim算法有了更深的了解，也使我对算法设计与分析更有兴趣，今后一定要更努力的学习这门课。