离散数学实验指导

1、实验1 关系的闭包运算1、实验类型：设计性2、实验目的通过算法设计并编程实现求给定关系的各种闭包运算，加深学生对闭包运算的概念的理解。3、实验内容给定关系R，求R的自反闭包、对称闭包及R的传递闭包。4、实验原理若关系R的关系矩阵为M，而自反闭包为A（即r（R）=A），对称闭包为B（即S（R）=B），则A=MI B=MMT 其中，I为恒等矩阵，MT为M的转置矩阵。5、实验仪器设备或软件环境及工具运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。6、实验要求复习关系闭包的定义，实验由一人一组完成。所编程序能够通过编译

2、，并能够实现求出给定关系的闭包的运算。7、实验报告要求（1）写出实验过程中遇到的问题及其解决过程。（2）写出类c的算法并编写一个程序求出给定关系的闭包。（3）写出实验结束时的程序清单及运行结果及实验总结。实验2 最小生成树的Kruskal算法1、实验类型：设计性2、实验目的通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。3、实验内容给定无向连通加权图，编程设计求出其一棵最小生成树。4、实验原理设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置

3、某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。5、实验仪器设备或软件环境及工具运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc、CFree(Windows)等C语言的编译环境。6、实验要求复习树及最小生成树的定义，实验由一人一组完成。所设计程序能够通过编译，并能够求出给定无向连通加权图的一棵最小生成树。7、实验步骤及注意事项（1） 边依小到大顺序得l1，l2，lm。（2） 置初值：S，0i，1j。（3） 若i=n-1，则转（6）。（4） 若生成树边集S并入一条新的边lj之后产生的回路

4、，则j+1j，并转（4）。（5） 否则，i+1i；ljS（i）；j+1j，转（3）。（6） 输出最小生成树S。（7） 结束。8、实验报告要求（1）写出实验过程中遇到的问题及其解决过程。（2）写出类c的算法，并写一个程序求出给定无向连通加权图的一棵最小生成树。（3）写出实验结束时的程序清单及运行结果及实验总结。参考例子：1闭包：#include int main()int i,j,k,n;static int str122,zifan122,chuandi122,duich122;printf(Please input the jie:n);scanf(%d,&n);printf(A=%dn,n

5、); for(i=0;in*n;i+)scanf(%d,&stri);printf(The shu zu is:n);for(j=0;jn*n;j+)printf(%4d,strj);if(j+1)%n=0)printf(n);for(j=0;jn*n;j+) zifanj=strj; chuandij=strj; duichj=strj;printf(The zifan bibao is:n);for(i=0;in*n;i+)if(i%(n+1)=0)zifani=zifani|1; printf(%4d,zifani);if(i+1)%n=0)printf(n);printf(The du

6、ich bibao is:n); for(i=0,j=0;in*n&jj*(n+1)&i=(j+1)*n)j+;for(i=0;in*n;i+)printf(%4d,duichi);if(i+1)%n=0)printf(n); printf(The chuandi bibao is:n);for(i=0;in;i+)for(j=0;jn;j+)if(chuandij*n+i)for(k=0;kn;k+) chuandij*n+k=chuandij*n+k|chuandii*n+k; for(i=0;in*n;i+)printf(%4d,chuandii);if(i+1)%n=0) printf

7、(n);return 0;2、warshall算法：#include #include #include #define N 3#define TRUE 0int get_matrix(int aNN) int i = 0,j = 0; for (i = 0;i N;i+) for (j = 0;j N;j+) scanf(%d,&aij); if (aij != 0 & aij != 1) printf(0 or 1 in matrixn); exit(2); return TRUE;int output_matrix(int aNN) int i = 0,j = 0; for (i = 0

8、;i N;i+) for (j = 0;j N;j+) printf(%d ,aij); putchar(n); return TRUE;int warshall(int aNN) int col = 0; int line = 0; int temp = 0; for (col = 0;col N;col+) for (line = 0;line N;line+) if (alinecol != 0) for (temp = 0;temp N;temp+) alinetemp = alinetemp | acoltemp; return TRUE;int main(void) int aNN

9、 = 0; printf(please input a matrix with %d * %d:n,N,N); if (get_matrix(a) printf(get matrix error!n); exit(1); warshall(a); output_matrix(a); return 0;3、Kruskal算法1:#define MAXE 11#define MAXV 10#include stdio.htypedef struct int vex1; /边的起始顶点 int vex2; /边的终止顶点 int weight; /边的权值 Edge;void kruskal(Edg

10、e E,int n,int e) int i,j,m1,m2,sn1,sn2,k; int vsetMAXV; for (i=1; i=n; i+) /初始化辅助数组 vseti=i; k=1; /表示当前构造最小生成树的第k条边，初值为1 j=0; /E中边的下标，初值为0 while (k =6) break; for (i=1; i=n; i+) /两个集合统一编号 if (vseti=sn2) /集合编号为sn2的改为sn1 vseti=sn1; /if j+; /扫描下一条边 /while/kruskalint main() Edge EMAXE; int nume,numn;/*

11、printf(输入边数和顶数:n); scanf(%d%d,&nume,&numn);*/ nume=10; numn=6;/ printf(请输入各边及对应的的权值(起始顶点 终止顶点 权值)n);/* for(int i=0; imaxver|num0) printf(Error!Please reinput!n); goto restart; for(j=0; jnum; j+) for(k=0; knum; k+) if(j=k) Gjk=maxright; usedjk=1; touchedjk=0; else if(j=maxright|temp-1) printf(Invalid

12、 input!n); goto re; if(temp=-1) temp=maxright; Gjk=Gkj=temp; usedjk=usedkj=0; touchedjk=touchedkj=0; for(j=0; jnum; j+) pathj0=0; pathj1=0; for(j=0; jnum; j+) status=0; for(k=0; knum; k+) if(Gjkmaxright) status=1; break; if(status=0) break; for(i=0; inum-1&status; i+) for(j=0; jnum; j+) for(k=0; knu

13、m; k+) if(Gjkmin&!usedjk) v1=j; v2=k; min=Gjk; if(!usedv1v2) usedv1v2=1; usedv2v1=1; touchedv1v2=1; touchedv2v1=1; pathi0=v1; pathi1=v2; for(t=0; trecord; t+) FindCircle(patht0,patht0,num,patht0); if(circle) /*if a circle exsits,roll back*/ circle=0; i-; exsit=0; touchedv1v2=0; touchedv2v1=0; min=maxright; else record+; min=maxright; if(!status) printf(We cannot deal with it because the graph is not connected!n); else for(i=0; inum-1; i+) printf(Path %d:vertex %d to vertex %dn,i+1,pathi0+1,pathi1+1); return 1;int FindCircle(int start,int begin,int times,int