沃舍尔算法求java代码 沃舍尔算法示意图

什么是沃舍尔算法

用来计算关系的传递闭包的一种高效率算法，

专注于为中小企业提供做网站、成都做网站服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业管城免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了千余家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

比如说要求出n元素集合上关系的传递闭包使用2n³(n-1)次位运算，用沃舍尔算法只用2n³次位运算就可以求出

沃舍尔算法如何从m0算到m1

1. 首先是从定义出发的标准算法，若要求出包含关系R的最小的传递闭包，我们就要为R中的每一种可能传递的关系补完其可传递性。不同于自反和对称闭包，传递的复杂之处在于，他是可以有多重传递的，这就造成了初次补完R以后，新添加的关系有可能会和原有的关系一起产生新的传递关系（路径），这时候就需要二次补完。同样的道理，三次、四次...直到n次（n为R的顶点数）以后。

如上描述，求传递闭包的标准方法就是依次求出1、2、3...、n阶传递关系并在每阶求完之后与前一阶的矩阵联合，再进行下一阶的求解。具体的操作方法是对原矩阵MR（图7-11右）进行布尔幂运算。我们可以看到——MR[k] 的值mij正好是其前一阶，即MR[k-1] 的i行j列（或者说，顶点i和顶点j之间）传递关系存在与否的解。（难理解的话可以亲手算一算）

沃舍尔算法的路径和矩阵描述

2. 接着是沃舍尔算法，这个算法比前面的标准算法复杂度上少了一阶。沃舍尔算法使用了一条路径的“内点”的概念。即如a，b，c，.....，x样的一条路径，除去a和x之外的所有端点称为这条路径的内点。

具体的操作方法是以R为开头构造一系列（n个）矩阵，他们是W0 ,W1,W2,W3,W4 .....，其中W0= MR。这看起来和标准算法差不多，但是沃舍尔算法的高阶矩阵的值并不是由前一阶的布尔幂运算得来。而是这样定义的：Wk=[wij[k]]，如果存在一条从vi到vj的路径且这条路径的所有内点都在集合{v1，v2，....，vk}（表中的前k个顶点）内，那么wij[k]=1，否则为0.（注意有两个合取的条件）

可以看到，因为Wk-1中的“1”也必然满足于Wk，所以Wk-1中的“1”可以直接继承到Wk之中，即wij[k-1]=1→wij[k]=1。而对于Wk-1中的0，从前段的定义中我们可以看到，对于wij[k-1]为0，而wij[k]为1的情况，当且仅当wik[k-1]=1且wkj[k-1]=1。（或者使用路径的说法——存在一条从vi到vk和一条从vk到vj的路径，使得当内点集合扩大到vk时才满足了前段定义的第二条条件）注意这里的下标k，不再泛指k≤n的正整数，而是实指当前正在运算的Wk的k。举图7-11的例子来说明，W1的w24[1]的值应该是w21[0]*w14[0]=1，而在W0中这个位置的值是0.

总结来说，标准算法是通过n阶布尔幂来化简多重传递，并在过程中进行了矩阵合并的运算以保证所有路径都被保留；而沃舍尔算法在每阶矩阵的每个元素上，最多只进行2次布尔运算就可以取代标准算法的一个复杂度为O(n)的矩阵运算，因此效率得以提升。

离散数学沃舍尔算法怎么运算？

沃舍尔算法，得名于沃舍尔，他于1960年给出此算法。该算法能够有效的计算关系的传递闭包。沃舍尔算法只需要使用2n^3次位运算就可以求出传递闭包。

如图所示