图的的广度优先遍历

基本介绍

图的广度优先搜索，类似于一个分层的搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些节点的邻接结点。

广度优先遍历算法的步骤

访问初始节点V并且标记结点V为已访问

结点V入队列

当队列非空时，继续执行，否则算法结束
1. 出队列，取得队列的头结点U
2. 查找结点U的第一个邻接结点W
3. 若结点U的邻接结点W不存在，则转到步骤3：否则循环执行以下三个步骤
  - 若节点W尚且没有被访问，则访问结点W并且标记为已访问
  - 结点W入队列
  - 查找结点U的继W邻接结点后的下一个邻接结点W，转到步骤6

代码实现

//根据前一个邻接点的下标来获取下一个邻接点    /**     * 总共是分为两个结点，第一个节点是当前以此为基准进行遍历的点，     * 另外一个就是基准之外的需要一个一个进行遍历的所有的邻接点     * @param V1 v1是当前节点，在代表边的二维数组上，表示当前的行     * @param V2 V2是当前结点的已经走过的邻接结点     * @return 返回的应该是下一个要走的邻接结点     */    public int getNextNeighbor(int V1,int V2){
           for(int j = V2 + 1;j < Vertex.size();j ++){
               if(edges[V1][j] > 0){
                   return j;            }        }        return -1;    }    //得到第一个邻接结点的下标    /**     * 结合矩阵来看，传入的始索引，如果有边相连，那就返回对应的索引     * @param index  传给我第一个索引的下标     * @return 如果存在就返回对应的下标，如果没有那就返回-1     */    public int getFirstNeighbour(int index){
           //遍历整个list的索引，然后操作对应的二维数组，如果有关联的边，那就返回对应的索引        for (int i = 0;i < Vertex.size();i ++){
               //传入的索引作为对应的行数，然后在对应的行里继续进行遍历，如果查找到大于0的数，返回对应的            //索引，那就是与当前索引对应的有关联边的结点的索引            if (edges[index][i] > 0){
                   return i;            }        }        return -1;        //遍历完之后还是没有找到，返回-1说明没有找到对应的结点的索引    }

//将所有的结点都进行广度优先，    public void bfs(){
           for (int i = 0;i < getNumOfVertex();i ++){
               if(!isVisited[i]){
                   bfs(isVisited,i);            }        }    }    //对一个节点进行广度优先遍历的方法    private  void bfs(boolean[] isVisited,int index){
           int u;        //这个u表示队列的头结点对应的下标，        int w;        //表示邻接结点的下标        //队列，记录节点访问的顺序，        LinkedList queue = new LinkedList();        //访问节点，输出节点的信息        System.out.print(getVertexByIndex(index) + ">>");        //将访问过的点标记为已经访问过了        isVisited[index] = true;        //将访问过的结点加入队列        queue.addLast(index);        //加入循环条件        while (!queue.isEmpty()){
               u = (Integer)queue.removeFirst();            //得到第一个邻接点的下标            w = getFirstNeighbour(u);            while (w != -1){
                   //找到                //是否访问过                if (!isVisited[w]){
                       System.out.print(getVertexByIndex(w) + ">>");                    //标记已经访问过了                    isVisited[w] = true;                    //入队                    queue.addLast(w);                }                //以U为前一个结点，找W后面的下一个邻接点，                w = getNextNeighbor(u,w);                //找以u这一行，w的下一个节点                //体现广度优先的算法            }        }    }