[Algorithm] BFS

1. BFS (Breadth First Search, 너비 우선 탐색)

 

그래프 탐색 방법 중의 하나로 하나의 정점으로부터 시작해서 인접한 정점을 먼저 탐색하는 방법이다. 해당 정점과 연결되어있는 정점들 중 하나의 방향으로만 우선 탐색했던 DFS와 달리 BFS는 인접한 정점들을 먼저 탐색하고 이어서 다음으로 인접한 정점들을 탐색하는 방식으로, 깊이가 아닌 너비를 우선으로 탐색하는 방법이다. 주로 특정 정점까지의 최단 경로를 찾고 싶을 때 사용한다.

 

BFS는 인접한 노드들에 대해서 우선적으로 탐색하고 이어서 다음으로 인접한 노드들을 탐색하는 것이 트리 탐색의 level order traversal 과 유사한데,  그래프에서는 사이클이 발생할 수 있기에 방문한 노드를 확인하는 visited 를 구현하여 방문 여부를 확인하도록 구현한다.

 

 

2. BFS 구현

 

BFS는 인접한 노드들을 차례대로 저장하고 순서대로 출력할 수 있는 queue를 사용해서 구현한다. 시작점이 되는 루트 노드를 queue에 넣은 후 로직을 시작한다. 로직은 queue에 남아있는 요소가 더이상 없을때까지 반복하도록 한다. 하나의 노드를 큐에서 꺼낸 후 해당 노드를 기준으로 인접한 노드들을 탐색한다. 이때 이미 방문한 노드는 제외하고 탐색한다. 탐색된 노드들은 visited에 방문한 표시를 한 후 큐에 순서대로 넣는다. 이를 반복하여 큐에 더이상 남은 노드가 없을 때까지 진행한다.

 

DFS와 달리 queue를 이용하여 모든 노드를 방문할 때까지 iteration 하는 방식으로 구현된다.

 

- Java를 이용한 BFS 구현

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

import Algorithm.Graph.Graph;

public class BFS implements Graph {
    
    private int N;

    private boolean[] visited;

    private boolean[][] graph;

    public BFS(boolean[][] graph) {
        N = graph.length;
        this.visited = new boolean[N];
        this.graph = new boolean[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                this.graph[i][j] = graph[i][j];
            }
        }
    }

    public void bfs(int[] result, int index, int R) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(R);
        visited[R] = true;
        while(!queue.isEmpty()) {
            int current = queue.poll();
            for(int i = 0; i < N; i++) {
                if(!graph[current][i] || visited[i])
                    continue;
                visited[i] = true;
                result[index++] = i;
                queue.offer(i);
            }
        }
    }

    @Override
    public void search() {
        int[] result = new int[N];
        result[0] = 0;
        visited[0] = true;
        bfs(result, 1, 0);

        System.out.println("[BFS]");
        System.out.println(Arrays.toString(result));
    }
}

 

 

3. BFS의 시간 복잡도

 

BFS 는 그래프의 모든 정점, 간선을 조회한다.

그래프의 정점의 개수를 V, 간선의 개수를 E라고 할 때 DFS의 시간 복잡도는 O(V + E)가 된다.

 

 

[reference]

- https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

- https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

Breadth First Search or BFS for a Graph - GeeksforGeeks