图的连通性快速算法

介绍了一种新的图的连通性算法，用指引元表和相邻点表来描述图，用支援树生长法进行连通性广延搜索，其中又轮流使用二个堆栈来取用和存入本层及下一层的生长点，与传统算法相比，采用新算法可使时间开销从O（N^2)级降到O（NlnN)级，并通过实例对新算法进行了验证，同时本算法可推广应用于各种与图的连通性检查有关的问题，可望大大加快计算速度。

Speedy Algorithm forConnexity of Graph

Monte-Carlo method is usually adopted to calculate probabilities of connect between every node with source node of pipe net when estimating disaster of the pipe net due to earthquake. The hardcore of the method is check-up algorithm of the connexity of graph. The adjoint matrix is used as basic data structure describing the map in the traditional algorithm. If N is node number of pipe net, then the spending of time will be O ( N2 )-level. Thus it is not tolerable for great net. A new algorithm is introduced in this paper. A direct element table and a adjoin point table are used to describe the graph. A growth method of support tree is introduced to make extensive search of connexity. Therein two stacks are used alternately to get the growth point of current layer and deposit the growth point of next layer. Sequentially, the spending of time will be reduced O ( N ×lnN)-level. The new algorithm is used to calculate the probabilities of connect for water supply net of Puxi in Shanghai. The node and pipeline number of the net is 434 and 742 respectively. Simulated 100 000 times,about 6 minutes only are spent with Pentium 166 computer. This algorithm may be applied in various problems concerned with the connexity check of graph and should quicken greatly calculation speed.