5.32. Breadth-first traversal and shortest path

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

Page Views: 39 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 
                        

                    

                

            
        
        

            

    
        

            

                

                    
                        
                        
                            
Principles and Applications of WebGIS 

                        
                        
                             37
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Web框架 

                        
                        
                             942
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
WEB基础 

                        
                        
                             287
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Principles, Technologies, and Methods of Geographic Information Systems 

                        
                        
                             102
                        
                    
                    
                        

                            
 
 
 In recent years, Geographic Information Systems (GIS) have undergone rapid development in both theoretical and practical dimensions. GIS has been widely applied for modeling and decision-making support across various fields such as urban management, regional planning, and environmental remediation, establishing geographic information as a vital component of the information era. The introduction of the “Digital Earth” concept has further accelerated the advancement of GIS, which serves as its technical foundation. Concurrently, scholars have been dedicated to theoretical research in areas like spatial cognition, spatial data uncertainty, and the formalization of spatial relationships. This reflects the dual nature of GIS as both an applied technology and an academic discipline, with the two aspects forming a mutually reinforcing cycle of progress.