共 3 条
图的连通性快速算法
被引：15
作者：
陆鸣盛
沈成康
机构：
[1] 同济大学计算机科学与工程系
[2] 同济大学结构工程与防灾研究所 上海
[3] 上海
来源：
关键词：
图论;
连通性;
计算机算法;
地震;
灾害预估;
D O I：
暂无
中图分类号：
O157.5 [图论];
学科分类号：
070104 ;
摘要：
介绍了一种新的图的连通性算法 .用指引元表和相邻点表来描述图 ,用支撑树生长法进行连通性广延搜索 ,其中又轮流使用二个堆栈来取用和存入本层及下一层的生长点 .与传统算法相比 ,采用新算法可使时间开销从O(N2 )级降到O(NlnN)级 .并通过实例对新算法进行了验证 .同时本算法可推广应用于各种与图的连通性检查有关的问题 ,可望大大加快计算速度
引用
收藏
页码：436 / 439
页数：4
相关论文