Suppose we are given a digraph A. We need to calculate its connectivity digraph B.
I conceived two algorithms:
1.
Set X = A.
Loop
Set Y = X*A united with identity
Stop the loop if Y = X
Set X = Y
End loop
B = X
2.
Set X = A. [Or instead "X = A united with identity" and remove "united with identity" in the third step?]
Loop
Set Y = X*X united with identity [or should it be Y = (X united with identity)*(X united with identity)?]
Stop the loop if Y = X
Set X = Y
End loop
B = X
I think that the algorithms are equivalent but the second one is faster.
Are they really calculating connectivity and are really equivalent?
Is the second algorithm faster not only for incidence matrix representation but also for hash-map or like this representation of digraphs?
Is there an even more efficient algorithm?