离散数学实验指导

实验1关系的闭包运算1、实验类型：设计性2、实验目的通过算法设计并编程实现求给定关系的各种闭包运算，加深学生对闭包运算的概念的理解。3、实验内容给定关系R，求R的自反闭包、对称闭包及R的传递闭包。4、实验原理若关系R的关系矩阵为M，而自反闭包为A（即r（R）=A），对称闭包为B（即S（R）=B），则A=M∨IB=M∨MT其中，I为恒等矩阵，MT为M的转置矩阵。5、实验仪器设备或软件环境及工具运行Windows或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。6、实验要求复习关系闭包的定义，实验由一人一组完成。所编程序能够通过编译，并能够实现求出给定关系的闭包的运算。7、实验报告要求（1）写出实验过程中遇到的问题及其解决过程。（2）写出类c的算法并编写一个程序求出给定关系的闭包。（3）写出实验结束时的程序清单及运行结果及实验总结。实验2最小生成树的Kruskal算法1、实验类型：设计性2、实验目的通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。3、实验内容给定无向连通加权图，编程设计求出其一棵最小生成树。4、实验原理设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。5、实验仪器设备或软件环境及工具运行Windows或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc、CFree(Windows)等C语言的编译环境。6、实验要求复习树及最小生成树的定义，实验由一人一组完成。所设计程序能够通过编译，并能够求出给定无向连通加权图的一棵最小生成树。7、实验步骤及注意事项（1）边依小到大顺序得l1，l2，…，lm。（2）置初值：S，0i，1j。（3）若i=n-1，则转（6）。（4）若生成树边集S并入一条新的边lj之后产生的回路，则j+1j，并转（4）。（5）否则，i+1i；ljS（i）；j+1j，转（3）。（6）输出最小生成树S。（7）结束。8、实验报告要求（1）写出实验过程中遇到的问题及其解决过程。（2）写出类c的算法，并写一个程序求出给定无向连通加权图的一棵最小生成树。（3）写出实验结束时的程序清单及运行结果及实验总结。参考例子：1闭包：#includestdio.hintmain(){inti,j,k,n;staticintstr[122],zifan[122],chuandi[122],duich[122];printf(Pleaseinputthejie:\n);scanf(%d,&n);printf(A=%d\n,n);for(i=0;in*n;i++){scanf(%d,&str[i]);}printf(Theshuzuis:\n);for(j=0;jn*n;j++){printf(%4d,str[j]);if((j+1)%n==0)printf(\n);}for(j=0;jn*n;j++){zifan[j]=str[j];chuandi[j]=str[j];duich[j]=str[j];}printf(Thezifanbibaois:\n);for(i=0;in*n;i++){if(i%(n+1)==0)zifan[i]=zifan[i]||1;printf(%4d,zifan[i]);if((i+1)%n==0)printf(\n);}printf(Theduichbibaois:\n);for(i=0,j=0;in*n&&jn;i++){if(ij*(n+1)&&i(j+1)*n){duich[i]=duich[(i-j*(n+1))*(n-1)+i]||duich[i];duich[(i-j*(n+1))*(n-1)+i]=duich[(i-j*(n+1))*(n-1)+i]||duich[i];}elseif(i=(j+1)*n)j++;}for(i=0;in*n;i++){printf(%4d,duich[i]);if((i+1)%n==0)printf(\n);}printf(Thechuandibibaois:\n);for(i=0;in;i++)for(j=0;jn;j++)if(chuandi[j*n+i]){for(k=0;kn;k++)chuandi[j*n+k]=chuandi[j*n+k]||chuandi[i*n+k];}for(i=0;in*n;i++){printf(%4d,chuandi[i]);if((i+1)%n==0)printf(\n);}return0;}2、warshall算法：#includestdio.h#includestdlib.h#includeunistd.h#defineN3#defineTRUE0intget_matrix(inta[N][N]){inti=0,j=0;for(i=0;iN;i++){for(j=0;jN;j++){scanf(%d,&a[i][j]);if(a[i][j]!=0&&a[i][j]!=1){printf(0or1inmatrix\n);exit(2);}}}returnTRUE;}intoutput_matrix(inta[N][N]){inti=0,j=0;for(i=0;iN;i++){for(j=0;jN;j++){printf(%d,a[i][j]);}putchar('\n');}returnTRUE;}intwarshall(inta[N][N]){intcol=0;intline=0;inttemp=0;for(col=0;colN;col++){for(line=0;lineN;line++){if(a[line][col]!=0){for(temp=0;tempN;temp++){a[line][temp]=a[line][temp]|a[col][temp];}}}}returnTRUE;}intmain(void){inta[N][N]={0};printf(pleaseinputamatrixwith%d*%d:\n,N,N);if(get_matrix(a)){printf(getmatrixerror!\n);exit(1);}warshall(a);output_matrix(a);return0;}3、Kruskal算法1:#defineMAXE11#defineMAXV10#includestdio.htypedefstruct{intvex1;//边的起始顶点intvex2;//边的终止顶点intweight;//边的权值}Edge;voidkruskal(EdgeE[],intn,inte){inti,j,m1,m2,sn1,sn2,k;intvset[MAXV];for(i=1;i=n;i++)//初始化辅助数组vset[i]=i;k=1;//表示当前构造最小生成树的第k条边，初值为1j=0;//E中边的下标，初值为0while(ke)//生成的边数小于e时继续循环{m1=E[j].vex1;m2=E[j].vex2;//取一条边的两个邻接点sn1=vset[m1];sn2=vset[m2];//分别得到两个顶点所属的集合编号if(sn1!=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边{printf((v%d,v%d):%d\n,m1,m2,E[j].weight);k++;//生成边数增lif(k=6)break;for(i=1;i=n;i++)//两个集合统一编号if(vset[i]==sn2)//集合编号为sn2的改为sn1vset[i]=sn1;}//ifj++;//扫描下一条边}//while}//kruskalintmain(){EdgeE[MAXE];intnume,numn;/*printf(输入边数和顶数:\n);scanf(%d%d,&nume,&numn);*/nume=10;numn=6;//printf(请输入各边及对应的的权值(起始顶点终止顶点权值)\n);/*for(inti=0;inume;i++)scanf(%d%d%d,&E[i].vex1,&E[i].vex2,&E[i].weight);*///在这里对输入的数据进行排序，达到假设的要求，即：假设数组E存放图G中的//所有边，且边已按权值从小到大的顺序排列E[9].vex1=1;E[9].vex2=2;E[9].weight=6;E[0].vex1=1;E[0].vex2=3;E[0].weight=1;E[4].vex1=1;E[4].vex2=4;E[4].weight=5;E[6].vex1=2;E[6].vex2=3;E[6].weight=5;E[2].vex1=2;E[2].vex2=5;E[2].weight=3;E[8].vex1=1;E[8].vex2=2;E[8].weight=6;E[5].vex1=3;E[5].vex2=4;E[5].weight=5;E[7].vex1=3;E[7].vex2=5;E[7].weight=6;E[3].vex1=3;E[3].vex2=6;E[3].weight=4;E[1].vex1=4;E[1].vex2=6;E[1].weight=2;kruskal(E,numn,nume);}4、Kruskal算法2:#includestdio.h#definemaxver10#definemaxright100intG[maxver][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(Pleaseenterthenumberofvertex(s)inthegraph:\n);scanf(%d,&num);if(nummaxver||num0){printf(Error!Pleasereinput!\n);gotorestart;}for(j=0;jnum;j++)for(k=0;knum;k++){if(j==k){G[j][k]=maxright;used[j][k]=1;touched[j][k]=0;}elseif(jk){re:printf(Pleaseinputtherightbetweenvertex%dandvertex%d,ifnoedgeexistspleaseinput-1:\n,j+1,k+1);scanf(%d,&temp);if(temp=maxright||temp-1){printf(Invalidinput!\n);gotore;}if(temp==-1)temp=maxright;G[j][k]=G[k][j]=temp;used[j][k]=used[k][j]=0;touched[j][k]=touched[k][j]=0;}}for(j=0;jnum;j++){path[j][0]=0;path[j][1]=0;}for(j=0;jnum;j++){status=0;for(k=0;knum;k++)if(G[j][k]maxright){status=1;break;}if(status==0)break;}for(i=0;inum-1&&status;i++){f