In 1962, Warshall proposed an effective algorithm to find transitive closures of relationships. The specific process is as follows: the relation matrix of relation R is m on a finite set of n elements:

(1) Set the new matrix A = M；;

(2) Let k =1;

(3) If A[i, k]= 1 for all I's, then for j = 1 execute ... n:

A[i，j]←A[i，j]∨A[k，j]；

(4)k increases1;

(5) If k≤n, go to step (3), otherwise stop.

The obtained matrix A is the relation matrix of transitive closure t(R) of relation R. ..

The algorithm is mentioned in Discrete Mathematics edited by Zuo Xiaoling, but it is not explained. The following article will explain the idea of this algorithm in a more popular way.

2. explanation of 2.Warshall algorithm.

Let the graph of relation R be G, and let all vertices of graph G be v 1, v2, …, vn, then the graph of t(R) can be obtained in this way: If there is a path between any two vertices vi and vj in G, and there is no arc from vi to vj, an arc from vi to vj is added to graph G, and the transformed icon is G'. The adjacency matrix a of g' should satisfy that if there is a path from vi to vj in graph G, that is, vi is connected with vj, then A[i, j]= 1, otherwise A[i, j]=0.

In this way, the problem of finding t(R) becomes the problem of finding whether each pair of vertices in graph G is connected or not.

Define an n-order square matrix sequence A(0), A( 1), A(2), …, A(n), and the element value in each square matrix can only be 0 or 1. A(m)[i, j]= 1 indicates that there is a path from vi to vj, and the number of intermediate vertices is not more than m (m = 1...n), and A(m)[i, j]=0 indicates that there is no such path. And A(0)[i, j]= 1 means there is an arc from vi to vj, and A(0)[i, j]=0 means there is no arc from vi to vj.

In this way, A(n)[i, j]= 1 means that vi and vj are connected, and A(n)[i, j]=0 means that vi and vj are not connected. Therefore, A(n) is the relation matrix of t(R).

So how to calculate the square matrix sequence A(0), A( 1), A(2), …, A(n)?

Obviously, A(0)=M(M is the relation matrix of R).

If A(0)[i, 1]= 1 and A(0)[ 1, j]= 1, or A(0)[i, j]= 1, if and only if vi to vj.

Generally, if A(k- 1)[i, k]= 1 and A(k- 1)[k, j]= 1, or a (k- 1) [i, j] =. Expressed as:

A (k)[i，j]=(A(k- 1)[i，k]∧A(k- 1)[k，j])∨A(k- 1)[i，j] i，j，k= 1..n

In this way, the method of calculating A(k) can be obtained: first, assign A(k) to a (k-1); Then for all I = 1...n, if A(k)[i, k]= 1 (that is, A(k- 1)[i, k]= 1), for all j =1.

A (k)[i，j]←A(k)[i，j]∨A(k- 1)[k，j]

However, this is still far from step (3) in the aforementioned Warshall algorithm. If the above formula is changed to:

A(k)[i, j]←A(k)[i, j]∨A(k)[k, j] (that is, change A(k- 1)[k, j] to A(k)[k, j]).

The superscript k can be removed and the formula can be further changed to:

A[i，j]←A[i，j]∨A[k，j]

In this way, the calculation can be completed only by storing an n-order square matrix, and it is consistent with the formula of step (3) in the aforementioned Warshall algorithm. Then, can you change A(k- 1)[k, j] to A(k)[k, j]? The answer is yes. It will be proved that A(k-1) [k, j] is equal to A(k) [k, j] in the process of calculating a (k) (after the initial value of a (k) is given). The method of calculating A (k) can only change the value of A(k)[k, j] when i=k, and then the formula A (k) [i, j] ← A (k) [i, j] ∨ A (k- 1) [k, J]. The result of their summation is equal, so that any operation will not change the value of A(k)[k, j], so A(k- 1)[k, j] is equal to A(k)[k, j].

To sum up, an algorithm for calculating A(n) can be obtained, which is completely consistent with the aforementioned Warshall algorithm.

From the above analysis, it is not difficult to see that Warshall algorithm is similar to Floyd algorithm to find the shortest path between each pair of vertices in the graph. In fact, transitive closures of relationships can also be found by Floyd algorithm. The method is to make the weight of each arc in the graph G of relation R 1, so as to get a directed network G 1, and make the adjacency matrix of G 1 D(- 1) (if vi has no self-ring, then D(-65438+) because if vi in G is connected with vj,

References:

[1] Zuo Xiaoling, Li Weijian, Liu Yongcai, Discrete Mathematics, Shanghai: Shanghai Science and Technology Literature Publishing House, 1982.

[2] Yan Weimin, Wu Weimin, data structure C language version, Beijing: Tsinghua University Publishing House, 1997.