BFS(Breadth-First Search) 너비 우선 탐색 : 코드로 구현

2021.06.06 - [Java/알고리즘] - BFS(Breadth-First Search) 너비 우선 탐색 개념

 

1. BFS class

public class BFS {

    private int number;
    public int[][] matrix;

    private Queue<Integer> queue;
    private Stack<Integer> visited;
    private boolean[] visitBoolean;

    public BFS(int number){
        this.number = number;
        queue = new LinkedList<>();
        matrix = new int[number][number];
        visited = new Stack<>();
        visitBoolean = new boolean[number];
    }

    public void breadthFirstSearch(int start) {

        queue.add(start);
        visitBoolean[start] = true;

        int current;

        while (queue.size() >0) {
            System.out.println("queue : " + queue.toString());
            System.out.println("visited : " + visited.toString());
            current = queue.remove();
            visited.push(current);
            System.out.println("current : " + current);


                for (int j = 0; j < number; j++) {

                    if((matrix[current][j] !=0) && (visitBoolean[j]==false) ){
                        queue.add(j);
                      visitBoolean[j]=true;

                    }

                }


            if(visited.size() == number) {
                break;
            }

            System.out.println("-------------------");
        }

        System.out.println("-------------------");
        System.out.println("DFS 종료");
        System.out.println("queue : " + queue.toString());
        System.out.println("visited : " + visited.toString());
        System.out.println("방문여부 : " + Arrays.toString(visitBoolean));


    }
}

 

2. main

 

public class DFSPractice {

    public static void main(String[] args) {


        int number = 8;

        DepthFirstSearch DFS = new DepthFirstSearch(number);
        UndirectedGraph graph = new UndirectedGraph(number);
        BFS bfs  = new BFS(number);


        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1 ,3, 1);
        graph.addEdge(1 ,4, 1);
        graph.addEdge(2 ,5, 1);
        graph.addEdge(2 ,6, 1);
        graph.addEdge(4 ,5, 1);
        graph.addEdge(3 ,7, 1);

        //System.out.println(Arrays.deepToString(graph.getMatrix()));
        DFS.matrix = graph.getMatrix();
        bfs.matrix = graph.getMatrix();
       // DFS.dfsTraversal(4);
        bfs.breadthFirstSearch(0);



    }
}

 

3. 실행결과

queue : [0]
visited : []
current : 0
-------------------
queue : [1, 2]
visited : [0]
current : 1
-------------------
queue : [2, 3, 4]
visited : [0, 1]
current : 2
-------------------
queue : [3, 4, 5, 6]
visited : [0, 1, 2]
current : 3
-------------------
queue : [4, 5, 6, 7]
visited : [0, 1, 2, 3]
current : 4
-------------------
queue : [5, 6, 7]
visited : [0, 1, 2, 3, 4]
current : 5
-------------------
queue : [6, 7]
visited : [0, 1, 2, 3, 4, 5]
current : 6
-------------------
queue : [7]
visited : [0, 1, 2, 3, 4, 5, 6]
current : 7
-------------------
DFS 종료
queue : []
visited : [0, 1, 2, 3, 4, 5, 6, 7]
방문여부 : [true, true, true, true, true, true, true, true]