实验3贪心算法和回溯法

《实验3贪心算法和回溯法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验3贪心算法和回溯法一、实验目的1.理解最小生成树算法——Prim算法和Kruskal算法的基本思想，学会编程实现这两种算法；2.理解并查集的特点与适用环境，学会使用并查集解决常见的问题；3.理解单源最短路径算法——Dijkstra算法的基本思想，学会编程实现Dijkstra算法；4.理解回溯法的基本思想，学会使用回溯法解决常见的问题。二、实验内容1.编程实现Prim算法。输入：顶点编号及边权重。例：011002151250输出：最小生成树。例：01100215源代码：importjava.util.Scanner;pu

2、blicclassprim{publicstaticfinalintMAX1=100;publicstaticvoidmain(String[]args){floatc[][]={{0,0,10,15},{0,10,0,50},{0,1,50,0}};//1到2,101到3,152到3,50for(inti=1;i<=3;i++){for(intj=1;j<=3;j++){17c[i][j]=MAX1;//初始化两点之间的距离为无穷大}}prim(3,c);}publicstaticvoidprim(intn,float[

3、][]c){float[]lowcost=newfloat[n+1];//记录不在S中的顶点在S中的最近邻接点int[]closest=newint[n+1];//记录不在S中的顶点到S的最短距离，即到最近邻接点的权值boolean[]s=newboolean[n+1];//标记顶点是否被访问，访问过的顶点标记为trues[1]=true;//标记第一个点被访问过for(inti=2;i<=n;i++){lowcost[i]=c[1][i];//获取其他顶点到第一个点之间的距离closest[i]=1;s[i]=false

4、;}17for(inti=1;i

5、t[k]=j;}}}}}2.17在某个城市里住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？输入：第1行的第1个值表示总人数，第2个值表示总信息数；第2行开始为具体的认识关系信息。例：10423454858输出：单位个数。例：7源代码：importjava.util.Scanner;publicclassnpeople{finalstaticintMAX=100;//最大的结点的个数staticint[]parent;//结点的父结点static

6、int[]rank;publicnpeople(intx){for(inti=0;i

7、oidunion_set(intx,inty){x=find_set(x);y=find_set(y);if(rank[x]>rank[y]){parent[y]=x;}else{if(rank[x]==rank[y]){rank[y]++;}parent[x]=y;}}publicstaticvoidmain(String[]args){17parent=newint[MAX];rank=newint[MAX];Scannerscan=newScanner(System.in);intn,m;intx,y;n=scan.

8、nextInt();m=scan.nextInt();for(inti=0;i<=n;i++){parent[i]=i;}for(inti=1;i<=m;i++){x=scan.nextInt();y=scan.nextInt();union_set(x,y);}intcount=0;for(inti=