java数据结构和算法——图的广度优先（BFS）遍历

一、图的遍历介绍

• 所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略；
• 一般有两种访问策略: (1)深度优先遍历； (2)广度优先遍历。

二、图的广度优先搜索(Broad First Search)

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

三、图的广度优先遍历算法步骤

1. 访问初始结点v并标记结点v为已访问；
2. 结点v入队列；
3. 当队列非空时，继续执行，否则算法结束；
4. 出队列，取得队头结点u；
5. 查找结点u的第一个邻接结点w；
6. 结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤： 1)、若结点w尚未被访问，则访问结点w并标记为已访问； 2)、结点w入队列 ； 3)、查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

四、图的广度优先遍历示例需求

对下图进行广度优先搜索, 从1开始遍历.

五、图的广度优先遍历代码示例

1、定义一个图 类

package com.rf.springboot01.dataStructure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @description: 定义一个图 类
 * @author: xiaozhi
 * @create: 2020-10-28 21:11
 */
public class GraphBFS {

    private ArrayList vertexList;//存储顶点集合
    private int[][] edges;//存储图所对应的邻接矩阵
    private int numEdges;//表示边的数量
    private boolean[] isVisited;//定义一个boolean类型的数组,记录某个节点是否被访问

    //构造方法 n表示有多少个顶点
    public GraphBFS(int n){
        //初始化
        vertexList=new ArrayList(n);
        edges =new int[n][n];
        numEdges=0;
        isVisited=new boolean[5];
    }

    /**
     * @Description: 得到第一个邻接结点的下标 w
     * @param  index
     * @Author: xz
     * @return: 如果存在就返回对应的下标，否则返回-1
     * @Date: 2020/10/28 22:27
     */
    public int getFirstNodeIndex(int index){
        for(int j=0;j 0){
                return j;
            }
        }
        return -1;
    }
    /**
     * @Description: 根据前一个邻接结点的下标来获取下一个邻接结点
     * @Author: xz
     * @return: 如果存在就返回对应的下标，否则返回-1
     * @Date: 2020/10/28 22:38
     */
    public int getNextNodeIndex(int v1,int v2){
        for(int j=v2+1; j 0){
                return j;
            }
        }
        return -1;
    }

    /**
    * @Description:  广度优先遍历的方法
    * @param i   第一次就是 0
    *        isVisited  某个节点是否被访问
    * @Author: xz
    * @Date: 2020/10/28 22:20
    */
    private void bfsMethods(boolean[] isVisited, int i) {
        int u ; // 表示队列的头结点对应下标
        int w ; // 邻接结点w
        //队列，记录结点访问的顺序
        LinkedList queue = new LinkedList();
        //访问结点，输出结点信息
        System.out.print(getValueByIndex(i) + "=>");
        //标记为已访问
        isVisited[i] = true;
        //将结点加入队列
        queue.addLast(i);

        while( !queue.isEmpty()) {
            //取出队列的头结点下标
            u = (Integer)queue.removeFirst();
            //得到第一个邻接结点的下标 w
            w = getFirstNodeIndex(u);
            while(w != -1) {//找到
                //是否访问过
                if(!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + "=>");
                    //标记已经访问
                    isVisited[w] = true;
                    //入队
                    queue.addLast(w);
                }
                //以u为前驱点，找w后面的下一个邻结点
                w = getNextNodeIndex(u, w); //体现出我们的广度优先
            }
        }

    }

    /**
     * @Description: 重载bfsMethods方法
     * @Author: xz
     * @Date: 2020/10/28 22:47
     */
    public void bfsMethods() {
        isVisited = new boolean[vertexList.size()];
        for(int i = 0; i "A" 1->"B" 2->"C"
     * @Author: xz
     * @Date: 2020/10/28 22:31
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    /**
     * @Description: 返回v1和v2的权值
     * v1 表示点对应的的下标
     * v2 表示第二个顶点对应的下标
     * @Author: xz
     * @Date: 2020/10/28 22:34
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * @Description: 显示图对应的矩阵
     * @Author: xz
     * @Date: 2020/10/28 22:44
     */
    public void showGraph(){
        for(int[] link : edges) {
            System.err.println(Arrays.toString(link));
        }
    }
}

2、创建图的测试类

package com.rf.springboot01.dataStructure.graph;

/**
 * @description: 创建图的测试类
 * @author: xiaozhi
 * @create: 2020-10-28 23:11
 */
public class GraphBFSTest {
    public static void main(String[] args) {
        int n =8;//节点个数
        String vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};;//定义8个节点
        //1、创建图对象
        GraphBFS graphBFS = new GraphBFS(n);
        //2、循环添加顶点
        for(String vertex : vertexs){
            graphBFS.insertVertex(vertex);
        }
        //3、添加边的关系
        graphBFS.insertEdge(0, 1, 1);
        graphBFS.insertEdge(0, 2, 1);
        graphBFS.insertEdge(1, 3, 1);
        graphBFS.insertEdge(1, 4, 1);
        graphBFS.insertEdge(3, 7, 1);
        graphBFS.insertEdge(4, 7, 1);
        graphBFS.insertEdge(2, 5, 1);
        graphBFS.insertEdge(2, 6, 1);
        graphBFS.insertEdge(5, 6, 1);

       /* System.out.println("显示邻结矩阵============");
        graphBFS.showGraph();
*/

        System.out.println("广度优先遍历+++++++++++++++++");
        graphBFS.bfsMethods();
    }
}

3、运行测试类，输出结果如下：