[Algorithm] BFS

이번에도 마찬가지로 탐색 알고리즘 중 하나인 BFS에 대하여 공부해 보았습니다. BFS란 Breadth First Search의 줄임말로 '너비 우선 탐색' 즉, 가까운 노드부터 탐색하는 알고리즘입니다. DFS에서는 최대한 멀리 있는 깊은 노드를 우선적으로 탐색하였다면 BFS는 반대로 가까운 노드부터 탐색합니다. BFS를 구현할 때에는 Stack, 재귀 함수를 이용하는 것이 아니라 선입선출 방식인 큐 자료구조를 이용합니다. DFS에 다루었던 동일한 그래프로 BFS를 만들어 보겠습니다.

 

 

Stack(스택) - LIFO(Last In First Out)

DFS에서 썼던 그래프와 동일하므로 각 노드가 연결된 정보가 같습니다. 여기서 중요한 것은 DFS에서는 후입 선출 LIFO(Last In First Out) 였다면,

 

Queue(큐) - FIFO(First in First Out)

BFS에서는 FIFO(First In First Out)으로 먼저 들어온 값이 먼저 나가게 됩니다. 즉 Queue에 1을 삽입하고 방문 처리를 한 후에 1을 꺼내고 방문하지 않은 노드 2, 3, 8을 큐에 삽입하게 됩니다. 이와 같은 방법이 계속 반복되어 Queue에 남은 값이 없을 때까지 반복 수행합니다.

 

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

 

# deque(큐 자료구조)를 사용하기 위해 import
from collections import deque

def bfs(graph, start, visited):
	# 인자로 건내면 이를 deque화 시켜준다. 즉 시작 노드인 1을 deque에 넣어준다.
    queue = deque([start])
    
    # 시작노드는 방문하였기 때문에 방문 처리
    visited[start] = True
    
    # Queue에 값이 없을 때 까지 반복
    while queue:
    	# Queue에 들어있는 원소를 뽑는다.
    	v = queue.popleft()
        print(v, end=' ')
        
        # 해당 원소와 연결된 연결된 노드를 순회
        for i in graph[v]:
        	# 해당 원소와 연결된 노드를 방문하지 않았다면, Queue에 삽입
            if not visited[v]:
            	queue.append(v)
                # Queue에 삽입을 해주었기 때문에 방문 처리
                visited[i] = True
                
   
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
] 

visited = [False] * 9

bfs(graph, 1, visited)


'''
출력
1 2 3 8 7 4 5 6
'''

 

이번에 공부한 BFS는 DFS와 다르게 Queue(큐)라는 자료구조를 활용해서 구현할 수 있었다. DFS와 BFS의 개념들을 간단하게 공부하면서 둘의 차이점 깊이 우선 탐색과 너비 우선 탐색이라는 차이점을 알 수 있었고 BFS가 DFS보다 수행 시간이 더 좋다는 것을 알 수 있었다. DFS에서는 개념을 이해하는데 다소 시간이 많이 걸려서 그런지 BFS에서는 시간이 오래 걸리지는 않았던 것 같다.