An Efficient Algorithm to Determine the Connectivity of Complex Directed Networks

The connectivity is an essential property of the connections between the nodes in networks. The efficient determination algorithm for the connectivity of complex directed networks is an important research direction in graph theory. Aiming at the determination problem of the strong connectivity of directed networks, we propose an improved algorithm over the Warshall algorithm, which extends the research object to complex directed networks and has only the half time complexity of that of the latter. In addition, this article also takes the lead in research on the determination algorithm for the unilateral connectivity of complex directed networks, and on this basis, we propose an algorithm to efficiently determine the unilateral connectivity. Finally, the above two algorithms are integrated into a unified and efficient algorithm with the time complexity of $\mathcal {O}({n}^{3}+4.5{n}^{2})$. This algorithm can determine not only the strong connectivity but also the unilateral connectivity of complex directed networks.