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

Implementation and Comparison of Single Source Path Searching Algorithm

作　　者：冷劲夫[1] 胡燮[1] 胡颖 

机构地区：[1]中国地质大学(武汉)信息工程学院,湖北武汉430074 [2]湖北省测绘产品质量监督检验站,湖北武汉430071

出　　处：《地理空间信息》2010年第3期154-156,共3页Geospatial Information

摘　　要：单源路径搜索算法广泛应用于紧急出警、车载导航、物流配送和管线规划与设计等地理信息系统(GIS)相关领域。而在"连连看"游戏中,需要一种特殊的单源路径搜索方案,对此提出了一种算法,通过记录候选节点的转角数来筛选满足要求的路径。依据这一算法的两种实现策略-宽度优先搜索(BFS)和深度优先搜索(DFS),采用标准模板库(STL)技术,编写了相应的代码,并对这两种策略进行了详细的测试,比较了它们的实际搜索性能。Single source path searching algorithm has been widely applied in fields concerning GIS,such as emergency police,vehicle navigation,logistics delivery,pipeline planning and designing,etc.Considering the special single source path-searching requirement in match-maker game,we proposed an algorithm which would selected out appropriate paths by recording the turns of each candidate node.We coded according to two strategies-breadth-first search（BFS） and depth-first search（DFS）,and utilized standard template library（STL）,then made detailed test on them,and also made a comparison between their practical searching performance.

关 键 词：GIS 单源路径搜索 宽度优先搜索(BFS) 深度优先搜索(DFS) 

分 类 号：P208[天文地球—地图制图学与地理信息工程]