离散经典WARSHALL算法的C语言实现.pdf

《离散经典WARSHALL算法的C语言实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第22卷第5期长沙大学学报VoI．22NO．52008年9月JOURNALOFCHANGSHAUNIVERSITYSep．2008WarshaU算法的C语言实现郭志军(辽宁对外经贸学院信息技术系，辽宁大连116052)摘要：Warshall算法是求二元关系传递闭包的一种高效的算法．通过对二元关系可传递·t~-CJ研究，给出Warshalt算法的一个c语言程序，使对可传递性的研究变得更加直观和有效．关键词：传递；传递闭包；Warshall算法中图分类号：l1．1；O158文献标识码：A文章编号：1008—46

2、81(2008)05—0069—03二元关系是离散数学中一个重要内容，它是以(3)对上任何包含R的传递关系R，有Rc有序对为元素的集合．文献[]把关系的性质分为五R

3、．种：自反性、反自反性、对称性、反对称性、可传递性．一般将的传递闭包记为t(R)．传递闭包在计关系的性质明显地反映在它的关系矩阵上MR(如算机科学中有很多应用．例如，在计算机高级语言编表1所示)：译程序的语法分析中，常常要通过求定义在某字母表1二元关系性质的关系矩阵表示表上的有关语法规则的二元关系的传递闭包来计算非终极符所能导出的字符集[．引理

4、设为非空集合上的关系，则R是传递的当且仅当￡(R)=．定义3设A={II2，L，}，尺是A上的关系．令～r-：一f、【0若皿IT川，一一I'～2／-，，玎)J，从上表可以看出，通过关系矩阵中元素的性质／'11r12￡rln可以直接判别二元关系的自反性、反自反性、对称r21r21己r2n性、反对称性，并且很容易求出自反闭包和对称闭MM包．二元关系的可传递性的判别和求传递闭包是离1"n1rn2r散数学中的一个难点．传递闭包的求法有：集合法、是R的关系矩阵，记作MR．矩阵法、关系图法、Warshall(沃舍尔)算

5、法等，其中Warshall算法⋯1：Warshall算法是求传递闭包的一个较为有效的方输入：(R的关系矩阵)法．下面给出阐释．输出：Mr(t(R)的关系矩阵)1．Mr—M1准备知识2．fork1tondo定义l设为上的关系，若3．fori1tondoVVYVz(，Y，。∈AA<，Y>∈R^<4．彳bTj1tondoY，。>∈R一<，：>∈)，则称R为A上传递的5．Mr[i，J]一M7’[i，]+Mr[i，]·Mr[k，]关系．传递关系是一类很重要的二元关系．算法中矩阵加法和乘法中的元素相加都是使用定义2设尺

6、为非空集合A上的关系，的传递逻辑加．Mi，]表示为矩阵r，的i行j．列的元素．闭包是A上的关系尺，使得满足以下条件：2Warshall算法的一个C语言程序[3】(1)R是传递的(2)Rc#incllJde收稿日期：2008—05—09；修回日期：2008—09—01作者简介：郭志军(1978一)，男，辽宁新民人，辽宁对外经贸学院信息技术系讲师，硕士．研究方向：应用数学70长沙大学学报2008年9月#include运行Warshall算法程序，图1是C语言环境下voidmai

7、n()例1的运行结果(如图1所示)：{intA[10][10]；intn，i，j，k；prinf(”输入关系矩阵的维数n(n<10)＼n”)；scanf(”％d”，&n)；prinf(”输入n*n个数据(0or1)＼n”)；for(i-1；i<=n；i++){for(j=1；j<=n；j++){~anf(％d，，＆A[i][_j])；if(AIi][j]!=I~&AEi][j])图lC语言环境下例1运行的结果print_f(”Thereisanerror")；}r_l00I}求出了关系R的传递闭包7'：lL

8、l10l=f0r(i=1；i<=n；i++)l00j{MR，由引理可知是传递的．for(j=1；j<=n；j++)例2A={a，b，C，d}，R为A上的关系，R={{，，，，}，求尺的传递闭包并判断尺的传递性．{解R的关系矩阵为if(A[i][j]&&(A[i][k⋯A[j][k]))1100A[i][k]=1；001OMt~O1O001OO运行Warshall算法程序，图2是C语言环境下prinf(”传递闭包的关系矩阵：＼

9、n，)；例2的运行结果(如图2所示)：{_一一U奠I-●t蛋■一一一i!JIjfor(j=1；j<=n；j++)Ijprinf(”％2d”，A[i][J])；prinf(”＼n”)；}囊I}，该程序给出了求二元关系传递闭包的方法，再根据引理可以判断所给二元关系的有传递性．r3应用举例善_露’!。I⋯一例1A={1，2，3}，R为A上的关系，R={<●●_I_。；1，1>，<2，1>，<3，1>，<2，2>}，R的