BFS & DFS

bfs.java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TreeSearch {


    public static void depthFirstSearchWithStack(int[][] adjMatrix) {
        boolean[] visitors = new boolean[adjMatrix.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < adjMatrix.length; i++) {
            if (!visitors[i]) {
                stack.push(i);
                visitors[i] = true;
                System.out.println("arrived pos：" + (char) ('A' + i));
                while (!stack.isEmpty()) {
                    int k = stack.pop();
                    for (int j = 0; j < adjMatrix.length; j++) {
                        if (adjMatrix[k][j] != 0 && !visitors[j]) {
                            visitors[j] = true;
                            System.out.println("arrived pos：" + (char) ('A' + j));
                            stack.push(j);
                            break;
                        }
                    }
                }
            }
        }
    }


    public static void depthFirstSearch(int[][] adjMatrix) {
        boolean[] visitors = new boolean[adjMatrix.length];
        for (int i = 0; i < adjMatrix.length; i++) {
            if (!visitors[i]) {
                dfs(adjMatrix, visitors, i);
            }
        }
    }

    private static void dfs(int[][] adjMatrix, boolean[] visitors, int i) {
        System.out.println("arrived pos：" + (char) ('A' + i));
        visitors[i] = true;
        for (int j = 0; j < adjMatrix.length; j++) {
            if (!visitors[j] && adjMatrix[i][j] != 0) {
                dfs(adjMatrix, visitors, j);
            }
        }
    }


    public static void broadFirstSearch(int[][] adjMatrix) {
        boolean[] visitors = new boolean[adjMatrix.length];
        Queue<Integer> queue = new LinkedList<>();


        for (int i = 0; i < visitors.length; i++) {
            if (!visitors[i]) {
                visitors[i] = true;
                System.out.println("arrived pos：" + (char) ('A' + i));
                queue.add(i);

                while (!queue.isEmpty()) {
                    int k = queue.poll();
                    for (int j = 0; j < adjMatrix.length; j++) {
                        if (adjMatrix[k][j] != 0 && !visitors[j]) {
                            queue.add(j);
                            visitors[j] = true;
                            System.out.println("arrived pos：" + (char) ('A' + j));
                        }
                    }
                }
            }
        }
    }


    public static void main(String[] args) {
        int[][] adjMatrix = {
                {0, 0, 1, 1, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
                {1, 0, 0, 1, 0, 1, 0, 0, 0, 0},
                {1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
                {1, 1, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
                {0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
                {0, 0, 0, 0, 0, 0, 1, 0, 1, 0}};
        System.out.println("------ broadFirstSearch -------");
        TreeSearch.broadFirstSearch(adjMatrix);

        System.out.println("\n\n\n------ depthFirstSearch -------");
        TreeSearch.depthFirstSearch(adjMatrix);

        System.out.println("\n\n\n------ depthFirstSearch With Stack -------");
        TreeSearch.depthFirstSearchWithStack(adjMatrix);
    }
}