[알고리즘] 너비 우선 탐색(Breadth First Search, BFS)

너비 우선 탐색

• 루트노드(또는 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

  • 시작 정점(노드)으로부터 가까운 정점을 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

• 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법

  • 맹목적 탐색방법이란 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법

• 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용

• 너비 우선 탐색 알고리즘의 장점

  • 너비 우선 탐색은 출발노드에서 목표노드까지의 최단 길이 경로를 보장

• 너비 우선 탐색 알고리즘의 단점

  • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
    • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
    • 무한 그래프(infinite graph)의 경우에는 해를 찾지도 못하고, 끝내지도 못한다.

코드 설계

• 기준이 되는 노드의 상위 노드 검색, 없을 경우 인접 노드 검색
• 같은 레벨의 노드 검색 후, 해당 레벨 + 1의 인접 노드 검색
• 리스트를 확인할 수 있는 Queue, 방문 확인을 위한 visit 배열 생성
• 사용자가 입력한 기준 값으로 queue 넣고 해당 queue의 node 값에 인접한 adjacent node 리스트를 검색하여 방문 표시

코드 구현

• 인접행렬을 기반으로 한 너비 우선 탐색

public class GraphArr {

    private int[][] MATRIX; // 그래프 배열 선언

    public GraphArr() {}

    public GraphArr(int initSize) {
        this.MATRIX = new int[initSize + 1][initSize + 1];
    }

    public void put(int x, int y) {
        MATRIX[x][y] = MATRIX[y][x] = 1;
    }

    public void printGraph() {
        for (int i = 0; i < MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[i].length; j++) {
                System.out.print(MATRIX[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 너비 우선 탐색
     * @param V
     */
    private void bfs(int V) {

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[MATRIX.length]; // 간선 갯수

        queue.offer(V);
        visit[V] = true;

        while(!queue.isEmpty()) {
            int x = queue.poll(); // 방문한 노드를 큐에서 꺼내 인접한 모든 노드를 조회
            System.out.print(x + "\t");
            for(int i = 0 ; i < MATRIX.length ; i++) {

                if(!visit[i] && MATRIX[x][i] == 1) { // 간선확인, 노드 방문 여부 확인
                    visit[i] = true;
                    queue.offer(i);
                }
            }
        }
    }

    public static void main(String[] args) {

        int initSize = 7;

        GraphArr graph = new GraphArr(initSize);

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

        graph.printGraph();
        graph.bfs(1); /* 주어진 노드를 기준으로 BFS 탐색 */
    }
}

• 인접 배열 출력 및 BFS 탐색 결과

// 배열 출력
0 0 0 0 0 0 0 0 
0 0 1 1 0 0 0 0 
0 1 0 1 1 1 0 0 
0 1 1 0 0 0 1 1 
0 0 1 0 0 1 0 0 
0 0 1 0 1 0 0 0 
0 0 0 1 0 0 0 1 
0 0 0 1 0 0 1 0 
// BFS 탐색
1    2    3    4    5    6    7    

• 인접 리스트를 기반으로 한 너비 우선 탐색

public class GraphList {

    static class Graph {
        private int V;
        private LinkedList<Integer>[] adjacent;

        @SuppressWarnings("unchecked")
        public Graph(int V) {
            this.V = V;
            this.adjacent = new LinkedList[V];
            for (int i = 0; i < V; i++)  adjacent[i] = new LinkedList<>();
        }

        public void addEdge(Graph graph, int src, int dest) {
            graph.adjacent[src].add(dest);
            graph.adjacent[dest].add(src);
        }

        public void printGraph(Graph graph) {
            for (int v = 1; v < graph.V; v++) {
                System.out.println("Node [" + v + "]");
                System.out.print("adjacent Node: ");
                for (Integer node : graph.adjacent[v]) {
                    System.out.print("[" + node + "]\t");
                }
                System.out.println();
            }
        }

        /**
         * 너비 우선 탐색
         * @param start
         */
        public void bfs(int start) {
            boolean[] visit = new boolean[V];
            LinkedList<Integer> queue = new LinkedList<>();

            visit[start] = true;
            queue.offer(start);

            while(!queue.isEmpty()) {
                start = queue.poll();
                System.out.print(start + "\t");

                Iterator<Integer> i = adjacent[start].listIterator();
                while(i.hasNext()) {
                    int n = i.next();
                    if(!visit[n]) {
                        visit[n] = true;
                        queue.offer(n);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int initSize = 8;

        Graph graph = new Graph(initSize);

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

        graph.printGraph(graph);

        graph.bfs(1); /* 주어진 노드를 기준으로 BFS 탐색 */
    }
}

• 인접 리스트 출력 및 BFS 탐색 결과

// 기준 노드 및 인접 노드 출력
Node [1]
adjacent Node: [2]    [3]    
Node [2]
adjacent Node: [1]    [3]    [4]    [5]    
Node [3]
adjacent Node: [1]    [2]    [6]    [7]    
Node [4]
adjacent Node: [2]    [5]    
Node [5]
adjacent Node: [2]    [4]    
Node [6]
adjacent Node: [3]    [7]    
Node [7]
adjacent Node: [3]    [6]    
// BFS 탐색 1 기준
1    2    3    4    5    6    7

분석

• 인접 리스트 시간 복잡도
  • O(N+E)
• 인접 행렬 시간 복잡도
  • O(N^2)
• 그래프 내에 적은 숫자의 간선만을 갖는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리