基于回路结点收缩的有向图强连通判定算法

Algorithm of Identification on the Strongly Connexity of Digraph Based on Circuital Nodes Reducibility

介绍了一种将有向图中形成回路的结点进行收缩的方法来判断有向图是否连通。在有向图的邻接矩阵中,使用深度优先搜索(DFS)算法,找到一条回路后,将该回路中的结点收缩为一点,生成新的邻接矩阵,继续进行DFS搜索,直到没有回路。如果所有结点都收缩成一点,则该有向图是强连通的。

A new algorithm of identification the strongly connexity of digraph is described in this paper.In adjacency matrix of a directed graph,Deep_Fist Search（DFS）algorithm is used to find a circuit.These nodes in the circuit are reduced to one node to rebuild the adjacency matrix.Procedure is repeated until no circuit is found.Finally,if all nodes are reduced to one node,the directed graph exactly is strongly connected.