图的深度优先遍历bfs

拼搏现实的明天。 2024-04-19 09:04 64阅读 0赞

//带权图
    public class Graph { 
    
        private int vertexSize;//顶点数量
    
        private int[] vertexs;//顶点数组
    
        private int[][] matrix;//邻接矩阵 用于表示边
    
        //两个顶点之间没有边的时候的权值
        private static final int MAX_WEIGHT=-1;
    
        public void setMatrix(int[][] matrix) { 
            this.matrix = matrix;
        }
    
        //初始化参数
        public Graph(int vertexSize) { 
            this.vertexSize = vertexSize;
            vertexs = new int[vertexSize];
            for(int i=0;i<vertexSize;i++){ 
                vertexs[i]=i;
            }
            isVisited  = new boolean[vertexSize];
        }
    
    
        //获取某一顶点的第一个邻接点
        public int getFirstNeighbor(int vertex){ 
            int arr[]  = matrix[vertex];
            for(int i = 0;i<arr.length;i++){ 
                if(arr[i]!=0&&arr[i]!=MAX_WEIGHT){ 
                    return i;
                }
            }
            return -1;
        }
    
        //找vertex1的所有邻接点中vertex2邻接点的后一个邻接点
        public int getNextNeighbor(int vertex1,int vertex2){ 
            int arr[]  = matrix[vertex1];
            for(int i = 0;i<arr.length;i++){ 
                if(arr[i]!=0&&arr[i]!=MAX_WEIGHT&&i>vertex2){ 
                    return i;
                }
            }
            return -1;
        }
    
        //记录一个顶点是否已经被访问
        private boolean[] isVisited;
    
        //从vertex这个顶点开始遍历
        private void dfs(int vertex){ 
    
             isVisited[vertex]=true;
             int Neighbor = getFirstNeighbor(vertex);
             //如果vertex存在邻接点
             while(Neighbor!=-1){ 
                 //如果此邻接点没有被遍历过
                 if(!isVisited[Neighbor]){ 
                     //需要输出该邻接点
                     System.out.println(Neighbor);
                     dfs(Neighbor);
                 }
                 //获取Neighbor后的邻接点
                Neighbor = getNextNeighbor(vertex,Neighbor);
             }
        }
    
        //图的深度优先遍历
        public void dfs(){ 
            for(int i=0;i<vertexSize;i++){ 
                if(!isVisited[i]){ 
                    System.out.println(i);
                    dfs(i);
                }
            }
        }
    }