定義
傳遞閉包：即在數學中，在集合X上的二元關系R的傳遞閉包是包含R的X上的最小的傳遞關系，
相關問題
計算一個矩陣中的傳遞關系（如：圖上兩點之間的連通關系）
通常使用Warshall演算法進行計算
計算方法參考這個地址warshall
代碼實作
#include <stdio.h>
void warshall(int matrix[][100],int size){
//warshall
for(int j = 0; j < size; j ++){
for(int i = 0; i < size; i ++){
if(matrix[i][j] == 1){
for(int k = 0; k < size; k ++){
matrix[i][k] = matrix[j][k] || matrix[i][k];
}
}
}
}
}
int main(){
//輸入矩陣
int size;
scanf("%d",&size);
int matrix[100][100]={0};
for(int i = 0; i < size ; i ++){
for(int j = 0; j < size; j ++){
scanf("%d",&matrix[i][j]);
}
}
//warshall
warshall(matrix, size);
//輸出傳遞閉包
for(int i = 0; i < size ; i ++){
for(int j = 0; j < size; j ++){
printf("%d ", matrix[i][j]);
}
putchar('\n');
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/36275.html
標籤：C
上一篇：C----回圈
下一篇：藍橋杯-李白喝酒