5.32. Breadth-first traversal and shortest path

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

Page Views: 10 views

Breadth-first traversal starts from a vertex v, first visits the node and marks it as visited, then sequentially accesses all the unaccessed adjacencies {vi,..,vj} of node v and marks them as visited, and then repeats the access method of node v for each node in {vi,…,vj} until all nodes have been visited.

We can divide it into three steps:

  • （1）使用一个辅助队列 q，首先将顶点 v 入队，将其标记为已访问，然后循环检测队列是否为空。

  • （2）如果队列不为空，则取出队列第一个元素，并将与该元素相关联的所有未被访问的节点入队，将这些节点标记为已访问。

  • （3）如果队列为空，则说明已经按照广度优先遍历了所有的节点。

As shown in the following figure, the blue on the right shows the order of traversing nodes starting from 0, and the following is the distance of recording distance 0. It is known that breadth-first traversal can find the shortest path of the unauthorized graph.

image0

The following code shows how to use breadth-first traversal to complete traversal and query the shortest path. We add an array of global variables ord to the previous section of code to record the order of nodes in the path. Ord [i] Represents the order of I nodes in the path. At the same time, the constructor adjusts accordingly to ord each unaccessed node when traversing neighboring nodes. [i] = ord [v] + 1 record distance. The breadth-first traversal time complexity of adjacency table is O (VroomE), and the time complexity of adjacency matrix is O (V ^ 2).

... // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public ShortestPath(Graph graph, int s){ // 算法初始化 G = graph; assert s >= 0 && s < G.V(); visited = new boolean[G.V()]; from = new int[G.V()]; ord = new int[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ visited[i] = false; from[i] = -1; ord[i] = -1; } this.s = s; // 无向图最短路径算法, 从s开始广度优先遍历整张图 LinkedList q = new LinkedList(); q.push( s ); visited[s] = true; ord[s] = 0; while( !q.isEmpty() ){ int v = q.pop(); for( int i : G.adj(v) ) if( !visited[i] ){ q.push(i); visited[i] = true; from[i] = v; ord[i] = ord[v] + 1; } } } ...    
 Check the shortest path length from s point to w point. If it is unreachable from s to w, return-1. 
 
 
 
... public int length(int w){ assert w >= 0 && w < G.V(); return ord[w]; } ... 
 
 
 
 
  5.32.1.  Java instance code  
 
  源码包下载：   Download  
 
 
 Src/runoob/graph/ShortestPath.java file code:  
 
 
 
package runoob.graph; import runoob.graph.read.Graph; import java.util.LinkedList; import java.util.Stack; import java.util.Vector; /*\* \* 广度优先遍历与最短路径 */ public class ShortestPath { // 图的引用 private Graph G; // 起始点 private int s; // 记录dfs的过程中节点是否被访问 private boolean[] visited; // 记录路径, from[i]表示查找的路径上i的上一个节点 private int[] from; // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。 private int[] ord; // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public ShortestPath(Graph graph, int s){ // 算法初始化 G = graph; assert s >= 0 && s < G.V(); visited = new boolean[G.V()]; from = new int[G.V()]; ord = new int[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ visited[i] = false; from[i] = -1; ord[i] = -1; } this.s = s; // 无向图最短路径算法, 从s开始广度优先遍历整张图 LinkedList q = new LinkedList(); q.push( s ); visited[s] = true; ord[s] = 0; while( !q.isEmpty() ){ int v = q.pop(); for( int i : G.adj(v) ) if( !visited[i] ){ q.push(i); visited[i] = true; from[i] = v; ord[i] = ord[v] + 1; } } } // 查询从s点到w点是否有路径 public boolean hasPath(int w){ assert w >= 0 && w < G.V(); return visited[w]; } // 查询从s点到w点的路径, 存放在vec中 public 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点的路径 public 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(" -> "); } } // 查看从s点到w点的最短路径长度 // 若从s到w不可达，返回-1 public int length(int w){ assert w >= 0 && w < G.V(); return ord[w]; } }       
                
                

                    

                        

                            
                                文章链接
                            
                            ：
                            5.32. Breadth-first traversal and shortest path 
                        

                    

                

            
        
        

            

    
        
        

            

                

                    
                        
                            
                                Web框架 
                            
                            
                        
                             946
                        
                    
                    
                    
                        

                            
 
 
 

                        

                    
                

                
                

            

        
    
    
        
        

            

                

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

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

                        

                    
                

                
                

            

        
    
    
        
        

            

                

                    
                        
                            
                                WEB基础 
                            
                            
                        
                             289