[Algorithm] 너비 우선 탐색(BFS, Breadth-First Search)

너비 우선 탐색이란?

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

• 시작 노드로부터 가까운 노드를 먼저 방문하고 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 즉, 깊게(deep) 탐색 하기 전 넓게(wide) 탐색하는 방법
  
  

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이방법을 사용한다

 

너비 우선 탐색(BFS)의 특징

• 직관적이지 않을 수 있다
  • 시작 노드에서 시작해 거리에 따라 단계별로 탐색한다
• BFS 재귀적으로 동작하지 않는다
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다
  • 이를 검사하지 않으면 무한 루프에 빠질지도 모른다
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조 인 큐(Queue)를 사용한다
  • 선입선출을 원칙으로 하여 탐색한다
  • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다

 

너비 우선 탐색 과정

• Queue 인접점 우선
• 모든 인접 노드를 탐색하는 그래프 순회 알고리즘
• 가장 가까운 노드 선택 후, 탐색되지 않은 모든 노드 탐색
• 모든 노드의 모든 이웃을 탐색하고 각 노드가 정확히 한 번 방문된다

 

 

 

너비 우선 탐색(BFS) 구현

• 자료구조 큐(Queue)를 이용

BFS 의사코드

void search(Node root){
    Queue queue = new Queue();
    root.marked = true; // 방문한 노드 체크
    queue.enqueue(root); // 큐의 끝에 추가
    
    // 큐 소진 시까지 한다
    while(!queue.isEmpty()){
        Node r = queue.dequeue();  
        visit(r); // 큐에서 추출한 노드 방문
        // 큐에서 꺼낸 노드와 인접한 노드들을 차례로 방문
        foreach(Node n in r.adjacent) {
            if(n.marked == false){
                n.marked = true; // 방문한 노드 체크
                queue.enqueue(n);
            }
        }
    }
}

 

BFS 코드 구현

import java.io.*;
import java.util.*;

class Graph {
    private int V; // 노드 개수
    private LinkedList<Integer> adj[]; // 인접 리스트
    
    Graph(int v){
        V = v;
        adj = new LinkedList[v];
        for(int i=0;i<v;i++) // 인접리스트 초기화
            adj[i] = new LinkedList();
    }
    
    // 노드 연결
    void addEdge(int v, int w){
        adj[v].add(w);
    }
    
    // s를 시작 노드로 한 BFS로 탐색하면서 탐색한 노드 출력
    void BFS(int s) {
        // 노드의 방문 여부 판단 (초깃값 : false)
        boolean visited[] = new boolean[V];
        // BFS 구현을 위한 큐(Queue) 생성
        LinkedList<Integer> queue = new LinkedList<Integer>();
        
        // 현재 노드를 방문한 것으로 표시 후 큐에 삽입(enqueue)
        visited[s] = true;
        queue.add(s);
        
        // 큐가 빌 때까지 반복
        while(queue.size()!=0){
            // 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
            s = queue.poll();
            System.out.print(s+" ");
            
            // 방문한 노드와 인접한 모든 노드를 가져온다.
            Iterator<Integer> i = adj[s].listIterator();
            while(i.hashNext()){
                int n = i.next();
                
                // 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
                if(!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
        
    }
}

•  

public static void main(String args[]) {
    Graph g = new Graph(4);
    
    g.addEdge(0,1);
    g.addEdge(0,2);
    g.addEdge(1,2);
    g.addEdge(2,0);
    g.addEdge(2,3);
    g.addEdge(3,3);
    
    g.BFS(2);
}

 

너비 우선 탐색의 시간 복잡도

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)
• 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다