5.29. Adjacent node iterator

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

Page Views: 9 views

The most common operation in graph theory is to traverse adjacent edges, traversing related adjacent edges through a vertex. The time complexity of traversing the adjacent edges of the adjacency matrix is O (V), and the adjacency table can be found directly, which is more efficient.

image0

邻接矩阵迭代: 

... public Iterable<Integer> adj(int v) { assert v >= 0 && v < n; Vector<Integer> adjV = new Vector<Integer>(); for(int i = 0 ; i < n ; i ++ ) if( g[v][i] ) adjV.add(i); return adjV; } ...

邻接表迭代： 

... // 返回图中一个顶点的所有邻边 // 由于java使用引用机制，返回一个Vector不会带来额外开销, public Iterable adj(int v) { assert v >= 0 && v < n; return g[v]; } ...    
 For the expression of these two graphs, we can abstract an interface and generate the framework of this algorithm, regardless of whether the underlying layer is the adjacency table or the adjacency matrix. 
 
 This section writes a test case GraphReadTest, which can be viewed in the read package by calling the abstract interface implementation diagram. 
 
 
 
/*\* \* 图的抽象接口 */ public interface Graph { public int V(); public int E(); public void addEdge( int v , int w ); boolean hasEdge( int v , int w ); void show(); public Iterable<Integer> adj(int v); } 
 
 
 
 
  5.29.1.  Java instance code  
 
  源码包下载：   Download  
 
  （1）邻接矩阵迭代  
 
 
 Src/runoob/graph/DenseGraphIterater.java file code:  
 
 
 
package runoob.graph; import java.util.Vector; /*\* \* 邻接矩阵迭代 */ public class DenseGraphIterater { // 节点数 private int n; // 边数 private int m; // 是否为有向图 private boolean directed; // 图的具体数据 private boolean[][] g; // 构造函数 public DenseGraphIterater( int n , boolean directed ){ assert n >= 0; this.n = n; this.m = 0; this.directed = directed; // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边 // false为boolean型变量的默认值 g = new boolean[n][n]; } // 返回节点个数 public int V(){ return n;} // 返回边的个数 public int E(){ return m;} // 向图中添加一个边 public void addEdge( int v , int w ){ assert v >= 0 && v < n ; assert w >= 0 && w < n ; if( hasEdge( v , w ) ) return; g[v][w] = true; if( !directed ) g[w][v] = true; m ++; } // 验证图中是否有从v到w的边 boolean hasEdge( int v , int w ){ assert v >= 0 && v < n ; assert w >= 0 && w < n ; return g[v][w]; } // 返回图中一个顶点的所有邻边 // 由于java使用引用机制，返回一个Vector不会带来额外开销, public Iterable adj(int v) { assert v >= 0 && v < n; Vector adjV = new Vector(); for(int i = 0 ; i < n ; i ++ ) if( g[v][i] ) adjV.add(i); return adjV; } }    
  （2）邻接表迭代  
  
 
 Src/runoob/graph/SparseGraphIterater.java file code:  
 
 
 
package runoob.graph; import java.util.Vector; /*\* \* 邻接表迭代 */ public class SparseGraphIterater { private int n; // 节点数 private int m; // 边数 private boolean directed; // 是否为有向图 private Vector[] g; // 图的具体数据 // 构造函数 public SparseGraphIterater( int n , boolean directed ){ assert n >= 0; this.n = n; this.m = 0; // 初始化没有任何边 this.directed = directed; // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边 g = (Vector[])new Vector[n]; for(int i = 0 ; i < n ; i ++) g[i] = new Vector(); } public int V(){ return n;} // 返回节点个数 public int E(){ return m;} // 返回边的个数 // 向图中添加一个边 public void addEdge( int v, int w ){ assert v >= 0 && v < n ; assert w >= 0 && w < n ; g[v].add(w); if( v != w && !directed ) g[w].add(v); m ++; } // 验证图中是否有从v到w的边 boolean hasEdge( int v , int w ){ assert v >= 0 && v < n ; assert w >= 0 && w < n ; for( int i = 0 ; i < g[v].size() ; i ++ ) if( g[v].elementAt(i) == w ) return true; return false; } // 返回图中一个顶点的所有邻边 // 由于java使用引用机制，返回一个Vector不会带来额外开销, public Iterable adj(int v) { assert v >= 0 && v < n; return g[v]; } }       
                
                

                    

                        

                            
                                文章链接
                            
                            ：
                            5.29. Adjacent node iterator 
                        

                    

                

            
        
        

            

    
        
        

            

                

                    
                        
                            
                                Web框架 
                            
                            
                        
                             946
                        
                    
                    
                    
                        

                            
 
 
 

                        

                    
                

                
                

            

        
    
    
        
        

            

                

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

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

                        

                    
                

                
                

            

        
    
    
        
        

            

                

                    
                        
                            
                                WEB基础 
                            
                            
                        
                             289