单源路径搜索算法的实现及比较

• 作者: 冷劲夫 胡燮 胡颖
• 来源期刊: 地理空间信息
• 学科: 地球科学
• 关键词: GIS 单源路径搜索 宽度优先搜索(BFS) 深度优先搜索(DFS)
• 年，卷（期）: 2010,（3）
• 所属期刊栏目: 仪器与软件
• 页码范围: 154-156
• 分类号: P208
• 字数: 2209字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-4623.2010.03.051

摘要

单源路径搜索算法广泛应用于紧急出警、车载导航、物流配送和管线规划与设计等地理信息系统(GIS)相关领域.而在"连连看"游戏中,需要一种特殊的单源路径搜索方案,对此提出了一种算法,通过记录候选节点的转角数来筛选满足要求的路径.依据这一算法的两种实现策略一宽度优先搜索(BFS)和深度优先搜索(DFS),采用标准模板库(STL)技术,编写了相应的代码,并对这两种策略进行了详细的测试,比较了它们的实际搜索性能.