利用Warshall算法求二元關系的可傳遞閉包

1、離散數學實驗訓練學 院 計算機與信息技術學院 指導老師 景麗萍 學生姓名 謝昂 學 號 13281164 提交日期 2014年5月22日 利用Warshall算法求二元關系的可傳遞閉包學生：謝昂 指導老師：景麗萍一、設計方案簡介 設計一個程序實現求解關系R的傳遞閉包二、Warshall算法Warshall在1962年提出了一個求關系的傳遞閉包的有效算法。其具體過程如下，設在n個元素的有限集上關系R的關系矩陣為M：   （1）置新矩陣A=M;   （2）置k=1;   （3）對所有i如果Ai,k=

2、1，則對j=1.n執(zhí)行：                      Ai,jAi,jAk,j;   （4）k增1;   （5）如果kn，則轉到步驟（3），否則停止。所得的矩陣A即為關系R的傳遞閉包t(R)的關系矩陣。三、需求分析用戶要自己計算出二元關系的矩陣形式，輸入時要按矩陣輸入，從第一排第一個開始輸入，直到第一排全部輸入（每

3、兩個數字之間要輸入一個空格），然后按回車轉換到下一行，以同樣的形式輸入該行數字，全部輸入完成后按回車。然后會輸出一個矩陣就是所求的關系R的傳遞閉包矩陣。程序可以求任意關系R的傳遞閉包，但必須按要求輸入正確的關系矩陣形式。四、概要設計 在集合X上的二元關系R的傳遞閉包是包含R的X上的最小的傳遞關系。R的傳遞閉包在數字圖像處理的圖像和視覺基礎、圖的連通性描述等方面都是基本概念。一般用B表示定義在具有n個元素的集合X上關系R的n×n二值矩陣，則傳遞閉包的矩陣B*可如下計算：      B* = B&#

4、160;+ B2 + B3 + + (B)n     式中矩陣運算時所有乘法都用邏輯與代替，所有加法都用邏輯或代替。上式中的操作次序為B，B(B)，B(BB)，B(BBB)，所以在運算的每一步我們只需簡單地把現有結果乘以B，完成矩陣的n次乘法即可。五、主要實驗流程圖程序開始輸入矩陣的維數輸入矩陣各元素的值輸入是否正確?計算出可傳遞閉包關系矩陣打印可傳遞閉包的關系矩陣結束正確不正確六、實驗源代碼#include "stdio.h"void Warshall(int n

5、)int i , j, k;int temp100100;int is_correct=0;flag:while(is_correct=0)fflush(stdin);for(int a=0;a<n;a+)printf("請輸入矩陣第%d行元素:",a+1);for(int b=0;b<n;b+)scanf("%d",&tempab);if(tempab=0|tempab=1) /判斷輸入是否合法is_correct=1;elseis_correct=0;printf("矩陣輸入錯誤！請重新輸入n");goto f

6、lag;for(i=0;i<n;i+)for(j=0;j<n;j+)if(tempji=1)for(k=0;k<n;k+)tempjk=tempik|tempjk;printf("傳遞閉包關系矩陣t(R):n");for(i=0;i<n;i+) for(j=0;j<n;j+)printf("%dt", tempij);printf("n");int main(int argc, char* argv)int n;printf("請輸入關系矩陣的維數: ");scanf("%d",&n);Warshall(n);retur