[Algorithm] 탐색 알고리즘 BFS

오도원공육사·2021년 8월 22일

알고리즘

목록 보기

15/17

BFS - Breadth First Search

BFS는 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색한다면 BFS는 그 반대다. BFS의 구현은 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 큐에 넣으면 자연스럽게 먼저 들어온 것이 먼저 나가므로 가까운 노드부터 탐색을 진행할 수 있다.

BFS

탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

방문처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않도록 체크하는 것을 의미한다. 방문 처리를 통해 각 노드를 한 번씩만 처리할 수 있다.

* 단순 출력문제가 아닐 경우에는 큐에서 노드를 꺼낼 시 해당 노드에 대해 문제에서 요구하는 특정 동작을 수행한다.

예시

다음 그래프를 DFS 알고리즘으로 탐색해보자. 이때 탐색 시작 노드는 1번 노드이다. 인접 노드가 여러 개일 때는 일반적으로 번호가 낮은 것부터 우선한다.

step 1)

시작 노드 1을 큐에 넣고 방문처리한다.
큐 : [1]
방문 : 1

step 2)

큐에서 노드 1을 꺼내고 방문하지 않은 인접 노드 2, 3, 8을 모두 큐에 삽입하고 방문처리한다.
큐 : [2, 3, 8]
방문 : 1, 2, 3, 8

step 3)

큐에서 노드 2를 꺼내고 방문하지 않은 인접 노드 7을 큐에 넣고 방문처리한다.
큐: [3, 8, 7]
방문 : 1, 2, 3, 8, 7

step 4)

큐에서 노드 3을 꺼내고 방문하지 않은 인접노드 4, 8를 모두 큐에 삽입하고 방문처리를 한다.
큐: [8, 7, 4, 5]
방문 : 1, 2, 3, 8, 7, 4, 5

step 5)

큐에서 노드 8을 꺼내고 방문하지 않은 인접노드가 없으므로 무시한다.
큐: [7, 4, 5]
방문 : 1, 2, 3, 8, 7, 4, 5

step 6)

큐에서 노드 7을 꺼내고 방문하지 않은 인접노드 6을 큐에 삽입하고 방문처리한다.
큐: [4, 5, 6]
방문 : 1, 2, 3, 8, 7, 4, 5, 6

step 7)

남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 된다.
큐: [ ]
방문 : 1, 2, 3, 8, 7, 4, 5, 6

결과적으로 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6 순서가 된다.

너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다. 수행함에 있어서 O(N)의 시간복잡도를 가진다.

소스코드

파이썬

from collections import deque

# BFS 메서드 정의
def bfs(start, visited):
	q = deque([start]) # 큐 구현을 위해 deque 라이브러리 사용
	visited.add(start) # 시작 노드 방문처리

	# 큐가 빌 때까지 반복
	while q:
		v = q.popleft() # 큐에서 하나 원소를 뽑아 출력
		print(v, end=' ')

		# 해당 원소와 연결된 아직 방문하지 않은 원소들을 큐에 삽입
		for i in graph[v]:
			if i in visited:
				q.append(i)
				visited.add(i)

visited = set()
graph = {
   1: [2, 3, 8], # 1번 노드에 2, 3, 8번 노드가 연결되어있다.
   2: [1, 7],
   3: [1, 4, 5],
   4: [3, 5],
   5: [3, 4],
   6: [7],
   7: [2, 6, 8],
   8: [1, 7]
}

dfs(1)

C언어

#include <stdio.h>
 
int graph[1001][1001]={0}; // 그래프
int visit[1001]={0}; // 방문처리 배열, visit[v] == true : v는 방문했다.
int q[1001]; // 큐 자료구조

// BFS 함수 정의
void BFS(int v,int N){
		// front : pop 노드 가리키는 인덱스
		// rear : 큐의 끝
		// pop : 큐에서 꺼낸 노드
    int front=0, rear=0, pop, i;
    
    printf("%d ",v);
    q[front]=v; // 큐에 시작 노드 v 삽입
    rear++; // 큐의 끝 수정
    visit[v]=1; // 노드 방문처리
 
		// 큐가 빌 때까지
    while(front<rear){
        pop=q[front];
        front++;
        
        for(i=1;i<=N;i++){
            if(graph[pop][i]==1 && visit[i]==0){
                printf("%d ",i);
                q[rear]=i;
                rear++;
                visit[i]=1;
            }
        }
    }
 
    return;
}
        
 
 
int main(){
    int N,M,Start;
    int i,x,y;
 
    scanf("%d%d%d",&N,&M,&Start);
    
    for(i=0;i<M;i++){
        scanf("%d%d",&x,&y);
        graph[x][y]=1;
        graph[y][x]=1;
    }

    BFS(Start,N);
 
    return 0;
}