15. 그래프 탐색 (1) - BFS

그래프 탐색

그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

그래프 탐색은 크게 두가지 방법이 있다.

 

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

개요

한 시작 정점을 정해서 인접한 정점부터 모두 탐색하는 방식이다.

 

설계 모델

• 정의
  • Discover: 정점을 처음 방문한다.
  • Explore: 간선을 처음 이용한다.

 

• 정점의 구분
  • White: discover되지 않은 상태 즉, 처음에 모든 정점은 white 상태이다.
  • Gray: discover는 되었지만 정점에 대해서 Explore가 끝나지 않은 상태

               = Gray 정점의 인접 정점들 중 최소 한개는 white 정점인 상태

 

• • Black: discover되고 해당 정점에 대해 모든 Explore가 끝난 상태

               = Black 정점의 인접 정점들은 모두 Gray 혹은 Black 상태일 것이다.

 

 

• 정점의 색깔과 BFS의 동작 과정을 상응시키면 아래와 같다.

1. white인 정점 하나를 선택해 Gray로 색칠한다.
2. 그 정점의 모든 white neighbor를 discover한다.

3. 모든 인접 정점이 discover되면 선택한 Gray를 Black으로 색칠한다.

 

  cf> 인접 정점에 대한 정보는 adjacency list(인접 리스트)에서 얻을 수 있다.

 

 

의사 코드

BFS(G, s) // s: source vertex

	// 시작하는 정점을 제외한 모든 정점에 대해서
	// 각각의 모든 정점에 대해서 거리를 무한대로 두고 parent 정점을 비워둔다.
	for each vertex u : V-{s} {		
		d[u] = INF;
		p[u] = NULL;			//p[u]: u의 parent 정점
	}

	// init, 시작하는 정점을 선택했으므로 GRAY로 칠해주고,
	// 자기자신 까지의 거리는 0
	// 부모 정점은 없다.
	color[s] = GRAY;
	d[s] = 0;
	p[s] = NULL;
	queue Q; // BFS의 queue는 생성하고 비워둔다.

	// 시작 정점 s를 큐에 넣고 인접정점들을 탐색한다.
	ENQUEUE(Q, s)
        
    // 큐가 빌 때 까지 반복
    while (!Q.empty()) {
        
        // 큐에 있던 정점을 pop해온 것이 u라고 하자 (첫 번째 반복에는 시작정점 s가 되겠지?)
        // 첫 번째 반복은 u가 s라고 생각하고 흐름을 따라가보자.
        u = Q.pop();
        
        // 정점 u (s) 의 모든 인접정점에 대해서 반복한다.
        for each v : Adj[u] {     
            // 만약 인접정점 v가 WHITE이면 
            // GRAY로 칠하고
            // d[u]에서의 거리보다 1이 클 것이며
            // v의 부모는 u가 될 것이다.
            // 그리고 인접정점 v를 큐에 넣어준다.
            if (color[v] == WHITE) {
                color[v] = GRAY;
                d[v] = d[u] + 1;
                p[v] = u;
                ENQUEUE(Q, v);
            }
        }
        // u의 모든 인접정점에 대한 탐색이 끝나면 u를 BLACK으로 칠한다.
        color[u] = BLACK;
    }

 

동작 과정

 

시간복잡도

• 모든 정점을 큐에 한번씩 넣어야 한다. (WHITE -> GRAY): O(V)
• 모든 정점을 큐에서 한번씩 빼야 한다. (GRAY -> BLACK): O(V)
• 모든 정점의 인접리스트를 한번식 스캔해야 한다. : O(E)
• => 시간복잡도: O (V+E)

 

C++ 코드 (흐름을 따라가며 코드를 작성해보세요, 외우기 힘들다면 의사코드를 보면서 코드를 작성해 보세요.)

// 위에서는 정점의 색깔로 표시했지만 컴퓨터는 그럴 수 없기에 bool visit[] 배열을 사용한다.
// visit[x] = false 이면 WHITE, true이면 GRAY or BLACK 이다.
// 아래는 인접 리스트 일 때의 구현입니다. 인접 행렬 일 때의 구현도 작성해보세요!

#include <queue>
#include <vector>

using namespcae std;

bool visit[100];
vector <int> adj_list[100];
int d[100], p[100];

void bfs (int start) { 
    // init
    queue <int> bfs_queue; 
    bfs_queue.push(start); 
    visit[start] = true; 
    d[start] = 0;		// 최단거리 찾을 때
    p[start] = -1;		// 최단거리 경로 구성 할 때
    
    while(!q.empty()){ 
        int u = q.front(); 
        q.pop(); 
        
        // printf("%d ", u);    // 방문 순서를 출력해준다.
        for(int i = 0; i < adj_list[u].size(); i++) {
            int v = adj_list[u][i]; 
            if(!visit[v]) { 
                bfs_queue.push(v); 
                visit[v] = true;
                d[v] = d[u] + 1;
                p[v] = u
            } 
        } 
    } 
}

 

 

 

활용

• 최단경로, 최단거리: 자신의 부모 노드를 저장하면서 탐색하기 때문에 최단경로와 최단거리를 구해 볼 수 도 있다.