CAJ | 학술논문

介绍了一种新的图的连通性算法用指引元表和相邻点表来描述图，用支撑树生长法进行连通性广延搜索，其中又轮流使用二个堆栈来取用和存入本层及下一层的生长点.与传统算法相比，采用新算法可使时间开销从O(N2)级降到O(NlnN)级.并通过实例对新算法进行了验证.同时本算法可推广应用于各种与图的连通性检查有关的问题，可望大大加快计算速度.
개소료일충신적도적련통성산법용지인원표화상린점표래묘술도，용지탱수생장법진행련통성엄연수색，기중우륜류사용이개퇴잔래취용화존입본층급하일층적생장점.여전통산법상비，채용신산법가사시간개소종O(N2)급강도O(NlnN)급.병통과실례대신산법진행료험증.동시본산법가추엄응용우각충여도적련통성검사유관적문제，가망대대가쾌계산속도.
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.