图的连通性快速算法

• 作者: 沈成康 陆鸣盛
• 来源期刊: 同济大学学报(自然科学版)
• 学科: 数学
• 关键词: 图论 连通性 计算机算法 地震 灾害预估
• 年，卷（期）: 2001,（4）
• 页码范围: 436-439
• 页数: 4页
• 分类号: O157.5
• 字数: 4161字
• 语种: 中文
• DOI: 10.3321/j.issn:0253-374X.2001.04.012

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈成康	同济大学结构工程与防灾研究所	7	68	4.0	7.0
2	陆鸣盛	同济大学计算机科学与工程系	1	31	1.0	1.0