[알고리즘] BFS(Breadth-First Search) 탐색 알고리즘이란?

 

 

 

 

그래프란 노드(Node)가 있고 노드를 연결한 간선(Edge)이 있는 자료구조이다. 그래프를 완전탐색하는 기본적인 알고리즘은 DFS와 BFS이다.

 

탐색을 하려면 우선 자료구조가 정의되어야 한다.

 

그래프(Graph)는 두 가지 방식으로 표현된다.

 

1. 인접행렬( 2차원 배열 )

2. 인접리스트 ( 리스트 )

 

행렬은 '인덱스'가 있다. 인덱스는 랜덤엑세스를 가능하게 하여, 특정노드에 접근하는 속도가 빠르다. 하지만 배열구조로 쓰레기값이 들어있는 공간도 유지를 해야하기에 메모리낭비가 심하다.

 

인접리스트방식은 리스트 자료구조를 이용한다. '연결' 방식의 자료구조인 만큼, 특정 노드를 시작으로 인접노드를 순회하는 경우 유리하다. '인덱스'가 아닌 '주소'로 인접노드에 접근하니 메모리 낭비도 적다. 그러나 랜덤엑세스가 아닌 참조를 통한 접근을 하여 탐색속도가 느리다. 

 

 

BFS(Breadth-First Search) : 넓이우선탐색

 

넓이우선탐색은 큐(Queue)로 구현된다. 

 

큐는 FIFO(First In First Out)으로 먼저 PUSH된 노드가 먼저 POP된다. 그러므로 이전 방문한 노드를 기억하지 않는다. LIFO(Last In First Out)인 스택은 이전 방문노드를 기억하고 있어 깊이 우선 탐색이 가능하다. 

 

DFS(Depth-First Search) 탐색 알고리즘

( DFS 자세한 내용은 위 포스팅 참고 )

 

 

그러므로 특정노드의 인접노드를 먼저 탐색하는 방식은 큐(Queue)로 구현하는 것이 적당하다. 

 

 

 

 

1의 인접노드를 순회하여 큐에 넣는다. 

 

 

 

 

1은 POP되고 2의 인접노드를 PUSH한다. 

 

 

 

 

 

2는 POP되고 3의 인접노드를 PUSH한다. 

 

위 방식을 반복하여 그래프의 완전탐색을 수행한다.

 

 

코드구현

from collections import deque #deque import


#BFS 함수
def bfs(graph,start,visited):
    
    queue = deque([start]) #deque자료구조로 인수로 배열을 넣을 수 있다. ex) deque([1,3,4,5])
    visited[start] = True #방문이력 True
    
    while queue: #큐가 Empty 상태일때까지 반복
        pointer = queue.popleft() #큐에서 데이터 가져오기(pop)
        print(pointer, end=' ')

        for i in graph[pointer]: #인접노드 순회
            if not visited[i]: #방문이력이 없는 경우에만 큐에 PUSH
                queue.append(i)
                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 함수 호출
bfs(graph,1,visited)

 

 

참고자료

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서