查找图的传递闭包 [英] Finding the transitive closure of a graph

问题描述

我正在尝试计算图的传递闭包.让我们以该图为例(图片描述了图，其邻接关系和连通性矩阵):

I am trying to calculate a transitive closure of a graph. Let`s consider this graph as an example (the picture depicts the graph, its adjacency and connectivity matrix):

使用我在此页上找到的Warshall算法，可以生成此连接矩阵(=传递闭包?)，与图片中的矩阵不同:

Using Warshall's algorithm, which i found on this page, I generate this connectivity matrix (=transitive closure?), that is different from the one in the picture:

 01111
 01111
 01011
 01111
 01111

我还尝试使用此小程序，我得到了不同的结果:

I have also tried using this applet which also gives me a different result:

01111
01111
01111
01111
01111

所以我现在有点困惑，因为我不知道哪个矩阵是正确的矩阵.有人可以阐明我的问题吗?

So I'm a little confused right now, since I don't know which matrix is the right one. Can someone shed some light on my problem?

推荐答案

C(1,1):C(1,1)处的字母T表示在A的对角线上应该有Ts.

C(1,1): The letter T at C(1,1) implies that there should be Ts on the diagonal of A.

C(3,3):Warshall算法的一轮似乎只发现深度为2的可到达节点.由于需要三个边缘才能从其自身到达第三个节点，因此仅一轮是不够的.

C(3,3): One round of the Warshall algorithm only seems to find reachable nodes at a depth of two. Since it takes three edges to reach node number three from itself, one round is not enough.

这篇关于查找图的传递闭包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！