5.31. Path-finding algorithm

发布时间 ： 2025-10-25 13:35:42 UTC      

Page Views: 9 views

The pathfinding algorithm of a graph can also be realized by depth-first traversing the dfs to find the path of the graph graph from the starting s point to other points. In the implementation class of the previous section, add global variables from array to record the path, from [i] Represents the last node of I on the path to be looked up.

First, construct a function to initialize the initial condition of the pathfinding algorithm, from = new int [G.V()] And from = new int [G.V()] And set the default value in the loop, the visited array is all false,from, the array is all-1, and then the starting node is recursively processed by dfs.

... // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public Path(Graph graph, int s){ // 算法初始化 G = graph; assert s >= 0 && s < G.V(); visited = new boolean[G.V()]; from = new int[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ visited[i] = false; from[i] = -1; } this.s = s; // 寻路算法 dfs(s); } ...

Then to determine whether there is a path from point s to point w, just query the corresponding array values of visited.

... boolean hasPath(int w){ assert w >= 0 && w < G.V(); return visited[w]; } ...

To get the specific path from s point to w point, we use the path method to realize it. We can first judge whether it is connected or not. We can call the hasPath method. From the constructor, we can know that all the paths can be found only by tracing up through the from array.

... Vector path(int w){ assert hasPath(w) ; Stack s = new Stack(); // 通过from数组逆向查找到从s到w的路径, 存放到栈中 int p = w; while( p != -1 ){ s.push(p); p = from[p]; } // 从栈中依次取出元素, 获得顺序的从s到w的路径 Vector res = new Vector(); while( !s.empty() ) res.add( s.pop() ); return res; } ...    
 
  5.31.1.  Java instance code  
 
  源码包下载：   Download  
 
 
 Src/runoob/graph/Path.java file code:  
 
 
 
package runoob.graph; import runoob.graph.read.Graph; import java.util.Stack; import java.util.Vector; /*\* \* 寻路 */ public class Path { // 图的引用 private Graph G; // 起始点 private int s; // 记录dfs的过程中节点是否被访问 private boolean[] visited; // 记录路径, from[i]表示查找的路径上i的上一个节点 private int[] from; // 图的深度优先遍历 private void dfs( int v ){ visited[v] = true; for( int i : G.adj(v) ) if( !visited[i] ){ from[i] = v; dfs(i); } } // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public Path(Graph graph, int s){ // 算法初始化 G = graph; assert s >= 0 && s < G.V(); visited = new boolean[G.V()]; from = new int[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ visited[i] = false; from[i] = -1; } this.s = s; // 寻路算法 dfs(s); } // 查询从s点到w点是否有路径 boolean hasPath(int w){ assert w >= 0 && w < G.V(); return visited[w]; } // 查询从s点到w点的路径, 存放在vec中 Vector path(int w){ assert hasPath(w) ; Stack s = new Stack(); // 通过from数组逆向查找到从s到w的路径, 存放到栈中 int p = w; while( p != -1 ){ s.push(p); p = from[p]; } // 从栈中依次取出元素, 获得顺序的从s到w的路径 Vector res = new Vector(); while( !s.empty() ) res.add( s.pop() ); return res; } // 打印出从s点到w点的路径 void showPath(int w){ assert hasPath(w) ; Vector vec = path(w); for( int i = 0 ; i < vec.size() ; i ++ ){ System.out.print(vec.elementAt(i)); if( i == vec.size() - 1 ) System.out.println(); else System.out.print(" -> "); } } }       
                
                

                    

                        

                            
                                文章链接
                            
                            ：
                            5.31. Path-finding algorithm 
                        

                    

                

            
        
        

            

    
        
        

            

                

                    
                        
                            
                                Web框架 
                            
                            
                        
                             946
                        
                    
                    
                    
                        

                            
 
 
 

                        

                    
                

                
                

            

        
    
    
        
        

            

                

                    
                        
                            
                                《地理信息系统原理、技术与方法》 
                            
                            
                        
                             97
                        
                    
                    
                    
                        

                            
 
 
 最近几年来，地理信息系统无论是在理论上还是应用上都处在一个飞速发展的阶段。 GIS被应用于多个领域的建模和决策支持，如城市管理、区划、环境整治等等，地理信息成为信息时代重要的组成部分之一； “数字地球”概念的提出，更进一步推动了作为其技术支撑的GIS的发展。 与此同时，一些学者致力于相关的理论研究，如空间感知、空间数据误差、空间关系的形式化等等。 这恰好说明了地理信息系统作为应用技术和学科的两个方面，并且这两个方面构成了相互促进的发展过程。 
 
 

                        

                    
                

                
                

            

        
    
    
        
        

            

                

                    
                        
                            
                                WEB基础 
                            
                            
                        
                             289