《实验一_传递闭包的实现》由会员分享，可在线阅读，更多相关《实验一_传递闭包的实现（3页珍藏版）》请在装配图网上搜索。
1、实验一 传递闭包算法一、实验目的1、理解关系矩阵作为布尔矩阵的逻辑运算2、通过编程深刻理解 Warshall 快速算法3、验证 Warshall 快速算法的正确性4、掌握 C 语言的编程技巧和方法二、实验内容用C语言编程实现传递闭包的Warshall快速算法三、实验原理(Warshall算法的原理)Mi,j表示关系R的关系矩阵M中元素若在关系R的关系图中存在从vi到vj的有向路径，则Mi,j=l；否则Mi,j=O。 定义：Mki,j=1 若在关系R的关系图中存在从vi到vj的有向路径，且这条路 上除了 vl, v2,-，vk外没有其它节点0 否则即M0i,j=1o在关系R的关系图中存在从vi到
2、vj的有向边M1i,j=1o在关系R的关系图中存在从vi到vj的有向路径,且这条路上除 了可能有 v1 外没有其它节点M2i,j=1o在关系R的关系图中存在从vi到vj的有向路径,且这条路上除 了可能有v1, v2外没有其它节点根据此定义，仅当下列两情形之一发生时， Mki,j=1(1) 存在从vi到vj的有向路径，且这条路上除了可能有v1, v2,-，vk-1 外没有其它节点。因此Mk-1i,j=1(2) 存在从 vi 到 vk 的有向路径和从 vk 到 vj 的有向路径,且每条路上除了 可能有v1, v2,-，vk-1外没有其它节点。因此Mk-1i,k=1 且 Mk-1k,j=1因此，Mk
3、i,j= Mk-1i,j v (Mk-1i,k=1 AMk-1k,j=1)四、实验要求 ：1、对输入的数据进行合法性检查,输入输出界面友好2、编写和调试完成程序3、保存和打印程序的运行结果五、实验步骤(一) 算法描述Step 1 初始化 MStep 2 刷新 M对 k=12,n 重复 Step 3 和 Step 4Step 3刷新行 对i=1,2,n 重复Step 4 Step 4 刷新 Mij 对 j=12,n 置 Mij=Mij v(MikAMkj )结束 Step 3循环结束 Step 2循环Step 5 退出（二）流程图（三）程序清单六、测试数据1、输入关系矩阵的传递闭包的关系矩阵：0、01001 11010100000100R2=010000， R3=00011 00000000、01000丿000000丿1 0 0、R1= 1 1 0b 0 0 0100、t(R1)=1100J000丿输出的结果应为：0t(R2)= 0,02、输出参考界面：111111 01011111111t(R3)=0001000000001、101 000000丿* TCput in the dimension:n-Jal01000 010 0 n-1010 0 0110000uIpsl T-l JS SJS1110011100110001100011000
实验一_传递闭包的实现
