BFS (Breadth First Search ) - 너비 우선 탐색

BFS (Breadth First Search ) - 너비 우선 탐색

그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.(=최단 경로)

 

기능	특징	시간복잡도(노드 수 : V, 에지 수 : E)
완전 탐색	Queue, FIFO 사용	O(V+E)

 

 

BFS 원리

1. 시작점을 구한고 자료구조(인접행렬or 인접리스트)를 초기화
2. BFS 호출 (큐에서 노드를 꺼낸 후 노드의 인접 노드를 다시 큐에 삽입, 값이 없을 때까지 반복)
3. 방문 여부 체크

 

코드

package com.java.coding;

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

public class BFSExam {
    public static void main(String[] args) {

        // 그래프를 2차원 배열로 표현
        // 인덱스와 노드를 일치 시키기 위해 0은 저장하지 않음
        // 1번 인덱스 = 1번 노드, 배열의 값은 연결된 노드
    	// 그래프 방향은 단방향
    	// 1. 초기화
        int[][] graph = {{}, // 0
        				{2,3}, // 1노드의 인접노드
        				{5,6}, // 2
        				{4},  // 3
        				{6},  // 4
        				{},  // 5
        				{}};  // 6

        // 1부터 시작점을 정해서 탐색
        // 2. bfs 호출
        System.out.println(bfs(1, graph));
        // 예상 결과값 : 1 -> 2 -> 3 -> 7 -> 5 -> 6 -> 4 -> 8 -> 
    }

    static String bfs(int start, int[][] graph) {
        StringBuilder sb = new StringBuilder();
        // 9개의 노드 그래프의 방문했는지 여부 
        boolean[] visit = new boolean[graph.length];
        // 3. 시작점 노드에서 시작하여 시작한 노드의 인접노드를 다시 넣기, 큐가 없을 때까지 반복
        // 4. 방문 여부 체크
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        visit[start] = true;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node + " -> ");
            // 큐에서 꺼낸 노드와 연결된 인접 노드들
            for (int i = 0; i < graph[node].length; i++) {
                int temp = graph[node][i];
                // 방문하지 않았으면 방문처리 후에 큐에 삽입
                if (!visit[temp]) {
                    visit[temp] = true;
                    queue.offer(temp);
                }
            }
        }
        return sb.toString();
    }
}