欢迎来到天天文库
浏览记录
ID:18833348
大小:75.39 KB
页数:14页
时间:2018-09-23
《算法设计与分析 贪心算法实验(2)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、实验7贪心算法实验(2)实验内容1.在某个城市里住着n个人,现在给定关于这n个人的m条信息(即某2个人认识)。假设所有认识的人一定属于同一个单位,请计算该城市有多少个单位?输入:第1行的第1个值表示总人数,第2个值表示总信息数;第2行开始为具体的认识关系信息。例:10423454858输出:单位个数。例:7源代码:#include#defineMAXV10#defineMAXE45typedefstruct{intvex1;intvex2;intweight;}edge;intmain(){voidkr
2、uskal(edgee[],intenu);inti,j;edgee[MAXE],temp;intnum;printf("pleaseenterthenumberofedge!");scanf("%d",&num);printf("pleaseentertheinfoofeachedge!");for(i=0;i3、e[i].weight>e[j].weight){temp=e[i];e[i]=e[j];14e[j]=temp;}}kruskal(e,num);system("pause");return0;}voidkruskal(edgee[],intenu){inti,j,k;intn1,n2,m1,m2;intvex[MAXV];for(i=1;i<=MAXV;i++)vex[i]=i;i=0;k=1;while(k4、f(m1!=m2){printf("%d-%d-%d",e[i].vex1,e[i].vex2,e[i].weight);if(k==enu)break;k++;for(j=0;j5、ver][maxver],record=0,touched[maxver][maxver]; intcircle=0; intFindCircle(int,int,int,int); intmain() { intpath[maxver][2],used[maxver][maxver]; inti,j,k,t,min=maxright,exsit=0; intv1,v2,num,temp,status=0; restart: printf("Pleaseenterthenumberof6、vertex(s)inthegraph:"); scanf("%d",&num); if(num>maxver7、8、num<0) { printf("Error!Pleasereinput!"); gotorestart; } for(j=0;j9、k) { re: printf("Pleaseinputtherightbetweenvertex%dandvertex%d,ifnoedgeexistspleaseinput-1:",j+1,k+1); scanf("%d",&temp); if(temp>=maxright10、11、temp<-1) { printf("Invalidinput!"); gotore;14 } if(temp==-1) temp=maxright; G[j][k]=G[k][j]=te12、mp; used[j][k]=used[k][j]=0; touched[j][k]=touched[k][j]=0; } } for(j=0;j
3、e[i].weight>e[j].weight){temp=e[i];e[i]=e[j];14e[j]=temp;}}kruskal(e,num);system("pause");return0;}voidkruskal(edgee[],intenu){inti,j,k;intn1,n2,m1,m2;intvex[MAXV];for(i=1;i<=MAXV;i++)vex[i]=i;i=0;k=1;while(k4、f(m1!=m2){printf("%d-%d-%d",e[i].vex1,e[i].vex2,e[i].weight);if(k==enu)break;k++;for(j=0;j5、ver][maxver],record=0,touched[maxver][maxver]; intcircle=0; intFindCircle(int,int,int,int); intmain() { intpath[maxver][2],used[maxver][maxver]; inti,j,k,t,min=maxright,exsit=0; intv1,v2,num,temp,status=0; restart: printf("Pleaseenterthenumberof6、vertex(s)inthegraph:"); scanf("%d",&num); if(num>maxver7、8、num<0) { printf("Error!Pleasereinput!"); gotorestart; } for(j=0;j9、k) { re: printf("Pleaseinputtherightbetweenvertex%dandvertex%d,ifnoedgeexistspleaseinput-1:",j+1,k+1); scanf("%d",&temp); if(temp>=maxright10、11、temp<-1) { printf("Invalidinput!"); gotore;14 } if(temp==-1) temp=maxright; G[j][k]=G[k][j]=te12、mp; used[j][k]=used[k][j]=0; touched[j][k]=touched[k][j]=0; } } for(j=0;j
4、f(m1!=m2){printf("%d-%d-%d",e[i].vex1,e[i].vex2,e[i].weight);if(k==enu)break;k++;for(j=0;j5、ver][maxver],record=0,touched[maxver][maxver]; intcircle=0; intFindCircle(int,int,int,int); intmain() { intpath[maxver][2],used[maxver][maxver]; inti,j,k,t,min=maxright,exsit=0; intv1,v2,num,temp,status=0; restart: printf("Pleaseenterthenumberof6、vertex(s)inthegraph:"); scanf("%d",&num); if(num>maxver7、8、num<0) { printf("Error!Pleasereinput!"); gotorestart; } for(j=0;j9、k) { re: printf("Pleaseinputtherightbetweenvertex%dandvertex%d,ifnoedgeexistspleaseinput-1:",j+1,k+1); scanf("%d",&temp); if(temp>=maxright10、11、temp<-1) { printf("Invalidinput!"); gotore;14 } if(temp==-1) temp=maxright; G[j][k]=G[k][j]=te12、mp; used[j][k]=used[k][j]=0; touched[j][k]=touched[k][j]=0; } } for(j=0;j
5、ver][maxver],record=0,touched[maxver][maxver]; intcircle=0; intFindCircle(int,int,int,int); intmain() { intpath[maxver][2],used[maxver][maxver]; inti,j,k,t,min=maxright,exsit=0; intv1,v2,num,temp,status=0; restart: printf("Pleaseenterthenumberof
6、vertex(s)inthegraph:"); scanf("%d",&num); if(num>maxver
7、
8、num<0) { printf("Error!Pleasereinput!"); gotorestart; } for(j=0;j9、k) { re: printf("Pleaseinputtherightbetweenvertex%dandvertex%d,ifnoedgeexistspleaseinput-1:",j+1,k+1); scanf("%d",&temp); if(temp>=maxright10、11、temp<-1) { printf("Invalidinput!"); gotore;14 } if(temp==-1) temp=maxright; G[j][k]=G[k][j]=te12、mp; used[j][k]=used[k][j]=0; touched[j][k]=touched[k][j]=0; } } for(j=0;j
9、k) { re: printf("Pleaseinputtherightbetweenvertex%dandvertex%d,ifnoedgeexistspleaseinput-1:",j+1,k+1); scanf("%d",&temp); if(temp>=maxright
10、
11、temp<-1) { printf("Invalidinput!"); gotore;14 } if(temp==-1) temp=maxright; G[j][k]=G[k][j]=te
12、mp; used[j][k]=used[k][j]=0; touched[j][k]=touched[k][j]=0; } } for(j=0;j
此文档下载收益归作者所有