【数论系列】 Warshall（沃舍尔）算法求传递闭包

2024-06-01 06:11| 来源: 网络整理| 查看: 265

一. 算法概述

1. 离散数学定义

2. Warshall算法

3. Warshall与floyd

二. 例题分析

一. 算法概述 1. 离散数学定义

在离散数学中，令关系集合为R^i，则所有元素的最终传递闭包为：

$t(R)=R \cup R^2 \cup R^3 \cup ... \cup R^n$

在图论中，令M^i为前i个节点的邻接矩阵/可达矩阵，则所有图节点的最终传递闭包的矩阵表示如下，其中+为逻辑加：

$M(R)=M+M^2+M^3+...+M^n$

2. Warshall算法

Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：

（1）置新矩阵A＝M；

（2）i＝1；

（3）对所有j执行，如果A[j，i]＝1，则对k＝1，2，…，n，令A[j，k]＝A[j，k]∨A[i，k]；

（4）i加1；（i是行，j是列）

（5）如果i≤n，则转到步骤（3），否则停止。、

不难理解，上述过程可以简化为对于每个相通的j - > i关系，我们可以从这个相通关系出发，看看能不能通过这条相通的j - > i来更新一下j - >k。对所有的可通关系都更新一遍M，最后的结果就是传递闭包了！其实现代码如下：

#include #include using namespace std; const int maxn = 100; int G[maxn][maxn];//离散数学定义法 int main() { int T; cin>>T; while(T--){ memset(G,0,sizeof(G)); int n,m; cin>>n>>m;//n个点m条边 for(int i = 1;i>a>>b; G[a][b] = 1;//建边 } for(int i =1;i

【本文地址】

公司简介

联系我们