warshall算法
warshall算法介绍
Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M： （1）置新矩阵A=M; （2）置i=1; （3）对所有j如果A[j,i]=1，则对k=1…n执行： A[j,k]=A[j,k]∨A[i,k]; （4）i加1; （5）如果i≤n，则转到步骤（3），否则停止。 所得的矩阵A即为关系R的传递闭包t®的关系矩阵。
举个小例子
输入矩阵M 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0输出传递闭包 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
来看看warshall算法具体的代码实现（C语言）
#include<string.h>
#include<stdio.h>
int M
[10][10];
int main(){
freopen("in.txt","r",stdin);
void jiexijuzheng(int n
);
memset(M
,0,sizeof(M
));
int a1
,i
,j
;
printf("输入个数：\n");
scanf("%d",&a1
);
printf("输入矩阵 ：\n");
for(i
=0;i
<a1
;i
++)
for(j
=0;j
<a1
;j
++) {
scanf("%d",&M
[i
][j
]);
}
jiexijuzheng(a1
);
printf("传递闭包：\n");
for(i
=0;i
<a1
;i
++){
for(j
=0;j
<a1
;j
++){
printf("-",M
[i
][j
]);}
printf("\n");
}
return 0;
}
void jiexijuzheng(int n
){
int i
,j
,k
;
for(i
=0;i
<n
;i
++){
for(j
=0;j
<n
;j
++){
if(M
[j
][i
]>=1){
for(k
=0;k
<n
;k
++){
M
[j
][k
]=M
[j
][k
]+M
[i
][k
];
}
}
}
}
for(i
=0;i
<n
;i
++){
for(j
=0;j
<n
;j
++){
if(M
[i
][j
]>1)M
[i
][j
]=1;
}}
}
总结
总的来讲这个warshall算法还是挺好实现的，算法翻译没啥障碍
