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