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

그래프에서 모든 정점을 방문하는 방법 중 하나인 너비 우선 탐색(Breadth-First Search, BFS)에 대해 공부하고자 한다. 그래프의 모든 정점을 방문하는 방법인 DFS와 BFS는 간단하지만 그래프의 알고리즘에서 핵심적인 위치를 차지한다. 따라서 반드시 알아야 할 알고리즘들 중 하나이며, 코딩테스트에도 빈번히 출제되는 유형이다.

 

출처: https://velog.io/@sukong/

루트를 시작으로 탐색을 한다면 BFS는 먼저 루트의 자식을 차례로 방문한다. 다음으로 루트의 자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 또 다음으로 루트에서 세 개의 간선을 거쳐서 도달할 수 있는 정점들 순으로 루트에서 거리 순으로 방문한다. (거리에 따라 단계별로 탐색한다.)

 

BFS는 두 노드 사이의 최단 경로(멀리 떨어진 노드는 나중에 탐색하기 때문), 임의의 경로를 찾을 때 주로 사용되곤 한다.

 

이 알고리즘은 그래프 탐색의 경우 어떤 노드를 방문했었는지 반드시 검사해야 한다. 그렇지 않으면 무한 루프에 빠질 위험이 있다.

BFS는 재귀적으로 동작하지 않으며 Queue를 사용한다. 방문한 노드들을 차례로 저장한 후 꺼낼 수 있기 위함이다. 즉 선입선출(First-In First-Out, FIFO)을 원칙으로 탐색한다.

Prim, Dijkstra 알고리즘과 유사하다.

 

* BFS의 시간 복잡도

인접 리스트로 표현된 그래프 : O(N + E)

인접 행렬로 표현된 그래프 : O(N^2)

 

DFS와 마찬가지로 그래프 내 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

 

그래프 구현 방식은 DFS와 마찬가지로 2가지가 있다.

• 인접 행렬
• 인접 리스트

 

* BFS 구현 알고리즘

• 루트 노드에서 시작
• 루트 노드와 인접하고 방문하지 않았으며, 큐에 저장되지 않은 정점을 큐에 저장한다.
• 큐에서 하나 꺼내어 가장 먼저 저장된 정점을 방문한다.

---

8개의 정점으로 이루어진 무향 그래프에서 BFS의 수행 과정을 보면 아래와 같다.

 

1) 시작 정점을 정점 1로 정하고 방문한다.

visit[1] = true

visit[2~8] = false

 

2) 정점 1에 인접한 정점을 모두 방문한다. (1 -> 2, 1 -> 3, 1 -> 4)

visit[1~4] = true

visit[5~8] = false

 

3)

 정점 2에 인접한 정점 중 방문하지 않은 정점은 없다.

 정점 3에 인접한 정점 중 방문하지 않은 정점을 방문한다. (3 -> 5)

 정점 4에 인접한 정점 중 방문하지 않은 정점을 모두 방문한다. 2개가 있다. (4 -> 6, 4 -> 7)

visit[1~7] = true

visit[8] = false

 

4)

 정점 5에 인접한 정점 중 방문하지 않은 정점은 없다.

 정점 6에 인접한 정점 중 방문하지 않은 정점 8을 방문한다. (6 -> 8)

 정점 7에 인접한 정점 중 방문하지 않은 정점은 없다.

 

5) 더 이상 방문할 정점이 없으므로 종료한다. 위 그래프에서 방문할 때 사용된 그래프만 남기면 아래 그림처럼 트리 형태가 되는데, 이 트리를 너비 우선 트리라 한다.

---

인접 행렬

	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	0	0	1	0	1
2	0	1	0	1	0	0	1	0	0
3	0	0	1	0	1	0	0	0	0
4	0	0	0	1	0	1	0	0	0
5	0	0	0	0	1	0	0	0	0
6	0	1	1	0	0	0	0	1	1
7	0	0	0	0	0	0	1	0	0
8	0	1	0	0	0	0	1	0	0

 

인접 리스트

1	2 - 6 - 8
2	1 - 3 - 6
3	2 - 4
4	3 - 5
5	4
6	1 - 2 - 7 - 8
7	6
8	1 - 6

 

* BFS 알고리즘

BFS(G, s) {
	//s : 시작 정점
    //Q : 큐
    //V : 정점 집합
    visit[s] -> true
    enqueue(Q, s)
    
    while(!Q.isEmpty()) then
    	u -> dequeue(Q)
        for v in L(u) then //L(u) : 정점 u의 인접 정점 집합
        	if(visit[v] = false) then
            	visit[v] = true
                enqueue(Q, v)
}                
        

# BFS 알고리즘 구현

    static int[][] graph;
    static boolean[] visit;
    static Queue<Integer> Q = new LinkedList<>();
    
    static void BFS(int start){

        visit[start] = true; //시작 정점 방문 완료
        System.out.printf("%d ", start);
        Q.add(start); //큐에 저장

        while(!Q.isEmpty()){
            int next = Q.poll(); //큐에서 뺌

            for(int a : graph[next]) //next정점의 인접 정점 순회
                if (a != 0 && !visit[a]) { //방문하지 않았으면
                    visit[a] = true; //방문 완료
                    System.out.printf("%d ", a);
                    Q.add(a); //큐에 저장
                }

        }
    }

 

 

☞ 참고 ----------------------------------------------------------------------------------------------------------------------

 

쉽게 배우는 알고리즘[개정판]

velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS-lp8zywtn

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