Warshall关系传递闭包
程序员文章站
2022-04-16 07:55:45
定义 传递闭包 :即在数学中,在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。 相关问题 计算一个矩阵中的传递关系(如:图上两点之间的连通关系) 通常使用Warshall算法进行计算 计算方法参考这个地址 "warshall" 代码实现 ......
定义
传递闭包:即在数学中,在集合x上的二元关系r的传递闭包是包含r的x上的最小的传递关系。
相关问题
计算一个矩阵中的传递关系(如:图上两点之间的连通关系)
通常使用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'); } }
上一篇: Python新手爬虫三:爬取PPT模板