由七牛笔试记一下连通图的几种判断方法

1.bfs

package QiNiuYun;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main2 {
    private static boolean isconnect(int N,int[][] tu){
        boolean ansflag = true;
        boolean[] isused = new boolean[N];
        List<Integer> jxlist = new ArrayList<>();//。队列
        isused[0] = true;//。首先选择一个开始节点，染成黑色（表示访问过）
        jxlist.add(0);//。将开始节点放入队列

        while (!jxlist.isEmpty()){
            int jx = jxlist.get(0);//。从队列首部选出一个顶点
            jxlist.remove(0);//。该选出的顶点从队头出队
            //。访问所有与该顶点邻接的点，访问后将该些邻接点染成黑色并按顺序入依次入队
            for (int i =0;i<N;i++){
                if (!isused[i] && tu[jx][i]!=0){
                    isused[i] = true;
                    jxlist.add(i);
                }
            }
        }

        for (int i=0;i<N;i++){
            if (!isused[i])
                ansflag = false;
        }

        return ansflag;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] tu = new int[N][N];
        for (int i=0;i<M;i++){
            int u = sc.nextInt(),v = sc.nextInt();
            tu[u-1][v-1] = 1;
            tu[v-1][u-1] = 1;
        }
        if (isconnect(N,tu)){
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
        sc.close();

    }
}

2.dfs_rec+dfs_stack

package QiNiuYun;

import java.util.Scanner;
import java.util.Stack;

public class Main3 {

    private static void dfs_rec(int start,boolean[] visited,int N,int[][] tu){
        visited[start] = true;
        for (int i =0;i<N;i++){
            if (!visited[i] && tu[start][i]!=0)
                dfs_rec(i,visited,N,tu);
        }
    }

    private static void dfs_stack(boolean[] visited,int N,int[][] tu){
        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        visited[0] = true;

        while (!stack.isEmpty()){
            boolean ispushed = false;
            int tmp = stack.peek();
            for (int i =0;i<N;i++){
                if (!visited[i] && tu[tmp][i]!=0){
                    visited[i] = true;
                    stack.add(i);
                    ispushed = true;
                    break;
                }
            }

            if (!ispushed) stack.pop();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean ans = true;
        int N = sc.nextInt(),M = sc.nextInt();
        int[][] tu = new int[N][N];
        boolean[] visited = new boolean[N];

        for (int i =0;i<M;i++){
            int u = sc.nextInt(), v = sc.nextInt();
            tu[u-1][v-1] = 1;
            tu[v-1][u-1] = 1;
        }

        for (int i =0;i<N;i++){
            if (visited[i])
                continue;
            dfs_rec(0,visited,N,tu);
        }

       for (boolean x:visited){
           if (!x) {
               ans = false;
               break;
           }
       }
        if (!ans)
            System.out.println("NO");
        else
            System.out.println("YES");
    }
}

3.判断欧拉回路（度为偶数；昨晚看错题目了，以为是欧拉回路，调了半天只过55.56%，今早起来仔细一想，题意只要判断连通。。。。）

package QiNiuYun;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static boolean isconnect(int N,int[][] tu){
        boolean ansflag = true;
        boolean[] isused = new boolean[N];
        List<Integer> jxlist = new ArrayList<>();
        isused[0] = true;
        jxlist.add(0);

        while (!jxlist.isEmpty()){
            int jx = jxlist.get(0);
            jxlist.remove(0);
            for (int i =0;i<N;i++){
                if (!isused[i] && tu[jx][i]!=0){
                    isused[i] = true;
                    jxlist.add(i);
                }
            }
         }

        for (int i=0;i<N;i++){
            if (!isused[i])
                ansflag = false;
        }

        return ansflag;
    }

    private static boolean iseven(int[] du){
        boolean ansflag = true;
        for (int i =0;i<du.length;i++){
            if (du[i]%2!=0){
                ansflag = false;
            }
        }
        return ansflag;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
                int N = sc.nextInt();
                int M = sc.nextInt();
                int[][] tu = new int[N][N];
                int[] du = new int[N];

                for (int i=0;i<M;i++){
                    int u = sc.nextInt(),v = sc.nextInt();

                    tu[u-1][v-1] = 1;
                    tu[v-1][u-1] = 1;

                    du[u-1]++;
                    du[v-1]++;

                }

                if (isconnect(N,tu) && iseven(du)){
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }
        sc.close();

    }
}

4.并查集正在学习中

#七牛云笔试##Java##学习路径#