〔传递闭包怎么求〕warshall算法求传递闭包怎么求

关于传递闭包，我想谈一下自己的想法，因为觉得这是个有用的东西，前几天上离散课中学到了传递闭包的概念，觉得在图论中还是有点用处的，就仔细想了一下，没想到还是很有收获的，最起码对于我对矩阵相乘有了更深的理解。之前学矩阵相乘的时候还是在线性代数中学到的，当时觉得不怎么具体，但是知道怎么用，直到听说矩阵相乘和图联系很大的时候也没多想，但是通过学传递闭包理解了他与图有啥联系。

不卖关子了，直接到正题。先说一下矩阵乘法吧，两个矩阵相乘，得到新的矩阵的某一个元素这样形如：<x,y>代表第 x行和第y列的元素。那么这个元素是怎么得到的呢，就是第一个矩阵的第x行和第二个矩阵的第y列相乘得到的！那么为了不搞的那么复杂我们就定义如果得到的数不为零记为1.否则就是0了。那么这有什么含义呢？其实都是人给的，好，我们就令<x,y>如果是1，就是代表x和y这两个点可以到达，并且是从x到y。那么矩阵相乘的时候就有意思了，可以看出相乘的时候第一个矩阵的元素<x1,y1>,x1是不是变的，同理第二个矩阵的元素的y2是不变的。那么我们就可以得到，最后如果得到的结果为1，即<x1,y2>为1。那么<x1,y2>就是可到达的，并且是从x1到y2。

到这里我想对于传递背包的理解就有一大半了。那么传递闭包是什么东西呢？就是形如一个集合，如果元素<x,y>、<y,z>在集合里，那么元素<x,z>也在集合里。放到图里就是说如果点x到y可到达，那么x和y就有一条边相连。放到矩阵里就是<x,y>是1。那么这个集合本身就是一个传递闭包。如果这个集合不满足这个性质呢？那么我们就要求他的传递闭包，让他变成一个“完整”的图。怎么求，一种方法就是用集合的复合来做，这是在离散课本上学到的，比较麻烦，但是考试会用到，呵呵。另一种方法用于编程，叫做warshall算法，可以用来解题，对于一个搞图论的人来说可以看看。在这里不多说。