用c语言编 一个关系的传递闭包
说明：以关系矩阵形式计算传递闭包： #include”stdio.h” #define N 1000 main() { int i,j,a[N][N],b[N][N],c[N][N],s=0,k,e[N][N],m,n; printf(“请输入你的关系矩阵的阶n(n=1000):\n”); scanf(“%d”,n); printf(“请输入你的关系矩阵:\n”); for(i=0;in;i++) for(j=0;jn;j++) { scanf(“%d”,a[i][j]); e[i][j]=a[i][j]; b[i][j]=a[i][j]; } for(m=1;mn;m++) { for(i=0;in;i++) for(j=0;jn;j++) { for(s=0,k=0;kn;k++) s+=b[i][k]*a[k][j]; c[i][j]=s; if(e[i][j]==0c[i][j]!=0) e[i][j]=c[i][j]; } for(i=0;in;i++) for(j=0;jn;j++) b[i][j]=c[i][j]; } for(i=0;in;i++) for(j=0;jn;j++) if(e[i][j]!=0) printf(“%d,%d,”,i+1,j+1); printf(“\n”); }
离散数学Warshall算法求传递闭包C语言实现？
#include stdio.h#include stdlib.h#define N 20#define M 20main(){ int i,j,k,m,n; int r1[M],r2[M],a[N],mr[N][N]={0}; FILE * fp; printf（＂程序自动调用c:/stone2.txt文件内相应数据\n＂）; fp=fopen(＂c:\\stone2.txt＂,＂r＂); fscanf(fp,＂%d＂,n)； /*读取集合元素个数*/ for(i=0;in;i++) /*读取集合元素*/ fscanf(fp,＂%d＂,a[i]); fscanf(fp,＂%d＂,m)； /*读取关系个数*/ for(k=0;km;k++) fscanf(fp,＂%d,%d＂,r1[k],r2[k])； /*读取关系*/ fclose(fp); printf（＂自反闭包r(R):\n{＂); for(i=0;in;i++) printf(＂%d,%d,＂,a[i],a[i])； /*输出自反闭包*/ for(k=0;km;k++) { if(r1[k]!=r2[k]) printf(＂%d,%d,＂,r1[k],r2[k]); else continue; } printf(＂\b}\n＂); printf（＂对称闭包s(R):\n{＂）； /*输出对称闭包*/ for(k=0;km;k++) { if(r1[k]!=r2[k]) printf(＂%d,%d,%d,%d,＂,r1[k],r2[k],r2[k],r1[k]); else printf(＂%d,%d,＂,r1[k],r2[k]); } printf(＂\b}\n＂); k=0; for(i=0;in,km;i++) { if(r1[k]!=a[i]) continue; else { for(j=0;jn,km;j++) /*关系转换成矩阵*/ { if(r2[k]!=a[j]) continue; else { mr[i][j]=1; k++; i=0;j=0; break; } } } } printf（＂关系所对应的关系矩阵：\n＂）; for(i=0;in;i++) { /*打印关系矩阵*/ for(j=0;jn;j++) printf(＂%5d＂,mr[i][j]); printf(＂\n＂); } for(k=0;kn;k++) for(i=0;in;i++) /*warshall*/ for(j=0;jn;j++) mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j]; for(i=0;in;i++) for(j=0;jn;j++) { /*把mr[]非0项赋值为1*/ if(!mr[i][j]) continue; else mr[i][j]=1; } printf（＂传递闭包对应关系矩阵：\n＂）; for(i=0;in;i++) { /*输出传递闭包对应的关系矩阵*/ for(j=0;jn;j++) printf(＂%5d＂,mr[i][j]); printf(＂\n＂); } system(＂PAUSE＂)；}自己写的，三个闭包都有，包括传递闭包，看注释就知道了，还是用文件读写，方便数据输入
编程：求一个关系的传递闭包（C语言）
利用关系的矩阵表示，可以通过Warshall算法计算有限集合上的二元关系的传递闭包。
求计算机求解关系R的传递闭包 C语言算法
传递闭包,最简单的技术是采用 【弗洛伊德算法】
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
1.若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
2.若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。
代码请见：
微信扫一扫 
支付宝扫一扫 
