Speedy Algorithm for Connexity of Graph
Ming Lu · Journal of Tongji University · 2001
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(N 2) 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 ×ln N ) 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.