BFS_图的连通性_java代码

解题思路:

用邻接矩阵存储每个顶点的出度（就是每个点到其它点有几个），bfs遍历每行，将每个点加入队列，再来个判断，判断每个点是否都走过

注意事项:

参考代码:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
  *  泸州职业技术学院
 * @BelongsProject Demo
 * @BelongsPackage PACKAGE_NAME
 * @Author lgb
 * @CreateTime 2022-06-08  21:21
 * @Description TODO 图，最重要的就是存储和遍历，这里用邻接矩阵存储，这里是无向图，bfs遍历
 * @Version 1.0
 * 思考：根据第一行输入判断下面会有多少行数据，当输入0结束
 * 这里的bfs不是走迷宫一样，上下左右，而是一行一行的遍历，判断所有顶点是否走过，连通性
 */
public class BFS_1732_连通图 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //顶点 和边
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        while (m != 0) {
            //邻接矩阵存放数据
            int[][] mm = new int[m][m];
            //用于判断是否每个顶点是否都走了。
            boolean[] bool = new boolean[m];
            //边
            for (int i = 0; i < n; i++) {
                int y = scanner.nextInt()-1;
                int x = scanner.nextInt()-1;
                //存放边 就是两个点互联,无向图
                mm[y][x] = 1;
                mm[x][y] = 1;
            }
            //一行的进行遍历,看看所有点是否都能走通(不是两个点必须联通，而是有路径可以走通)
            bfs(bool, mm);
            //下一组数据
            m = scanner.nextInt();
            n = scanner.nextInt();
        }

        //结束
        scanner.close();
    }

    public static void bfs(boolean[] bool, int[][] mm) {
        //创建队列
        Queue queue = new LinkedList();
        //初始化
        queue.add(0);//从第一行开始遍历
        bool[0] = true;//标记第一个顶点已走

        while (queue.size() != 0) {
            int n = queue.size();
            //每次都要遍历完上次的队列
            while (n > 0) {
                n--;
                //取出一个顶点
                int q = queue.poll();
                //遍历每一行
                for (int i=0; i<bool.length; i++) {
                    if (mm[q][i] == 1 && !bool[i] ) {
                        //下个顶点加入队列
                        queue.add(i);
                        //标记顶点已走
                        bool[i] = true;
                    }
                }
            }
        }
        //标记
        boolean flag = false;
        for (boolean b : bool) {
            if (!b) {
                flag = true;
                break;
            }
        }
        if (flag) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }
    }
}