너비 우선 탐색(BFS) 란?

그래프 탐색에는 2가지가 있다고 했는데 그 중에 하나인 BFS 탐색에 대해서 정리하려고 한다. 

 

 

너비 우선 탐색(breath first search : BFS) 

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 

 

 

 

위와 같은 그래프에서 화살표의 방향대로 탐색을 한다. (시작 정점에서 가까운 노드부터 탐색하는 것을 알 수 있다)

 

 

너비 우선 탐색을 위해서는?

• 가까운 거리에 있는 정점들을 차례로 정한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요함
• 무조건 큐에서 정점을 꺼내서 정점을 반물하고 인접 정점들을 큐에 추가한다.(큐가 소진될 때 까지 반복)

 

 

 

너비 우선 탐색 과정

 

https://yunyoung1819.tistory.com/86(그림 출처)

 

 

다시한번 정리하자면 다음과 같다.

 

• 위의 과정을 큐가 공백 상태가 될 때 까지 계속한다.
• 너비 우선 탐색의 특징은 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색을 진행된다는 것이다.
• 너비우선 탐색은 거리가 d인 정점들을 모두 방문한 다음, 거리가 (d+1)인 정점들을 모두 방문한다.
• BFS는 모든 가중치가 1일 때, 최단거리를 구하는 알고리즘이다.

 

너비 우선 탐색의 구현(인접 행렬 버전)

너비우선 탐색을 구현하는 방법은 2가지 이다. 하지만 여기서는 인접 행렬을 구현해보려 한다.

• 인접 행렬

import java.util.Queue;
import java.util.LinkedList;
 
public class GraphMatrix {
    boolean visited[];
    int V;  //정점의 수
    int adj[][];
 
    public GraphMatrix(int v){
        V = v;
        visited = new boolean[V];
        adj = new int[V][V];
    }
 
    void addEdge(int v1, int v2){
        if(v1 > V || v2 > V){
            System.out.println("잘못 됐습니다");
        }
        else{
            adj[v1][v2] = 1;
        }
    }
 
    void BFS(int v){  //인접행렬을 이용해서 BFS 구현하기
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(v);
        visited[v] = true;
        System.out.print(v + " ");
        while(!q.isEmpty()){
            v = q.poll();
            for(int w=0; w<V; w++){
                if(adj[v][w] ==1 && !visited[w]){
                    visited[w] = true;
                    System.out.print(w + " ");
                    q.offer(w);
                }
            }
        }
    }
}

 

 

 
public class Test {
    public static void main(String[] args){
        GraphMatrix m = new GraphMatrix(5);
 
        m.addEdge(0,1);
        m.addEdge(4,1);
        m.addEdge(4,3);
        m.addEdge(0,4);
        m.addEdge(0,3);
        m.addEdge(0,2);
        m.addEdge(1,2);
        m.addEdge(2,0);
        m.addEdge(2,3);
        m.addEdge(3,3);
 
        m.BFS(2);
    }
}

 

위와 같이 BFS 탐색은 자료구조 큐와 인접행렬을 이용해서 구현하였다.

구현조차도 쉽지 않다. 더 열심히 공부해서 손에 익게 만들어야 겠다.

 

 

 

너비 우선 탐색의 분석

정점의 수가 n이고 간선의 수가 e인 그래프인 경우 인접 리스트로 표현되어 있으면 전체 수행시간이 O(n+e)이며, 

인접행렬로 표현되어 있는 경우는 O(n*n) 시간이 걸린다. 

 

 

너비 우선 탐색도 깊이 우선 탐색과 같이 희소 그래프를 사용할 경우 인접리스트를 사용하는 것이 효율적이다. 

 

Q : 희소그래프란? 간선이 얼마 없는 그래프를 의미한다.