알고리즘 with 파이썬 (7) - BFS 너비 우선 탐색 개념

BFS는 큐 자료구조에 기초하여 구현이 간단하다. deque 라이브러리를 이용한다.

가까운 노드부터 탐색하는 알고리즘으로, 최대한 멀리있는 노드를 우선 탐색하는 DFS 와 반대이다.

인접 노드를 작은 순으로 큐에 담고, 다음 turn에서 빼므로 (선입선출) 자연스럽게 가까운 노드 순으로 방문하게 된다

DFS(깊이우선탐색) 보다 실제 수행시간이 짧다 = 빠르다.

 

1) 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다

2) 큐에서 노드를 꺼내, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.

3) 2)의 과정을 더이상 수행할 수 없을 때 까지 반복

 

이번에도 위 그래프를 너비우선탐색 방식으로 처리해보자

from collections import deque

#BFS 메서드 정의
def bfs(graph, start, visited):
    #큐 구현을 위해 deque라이브러리 사용
    queue = deque([start])
    #현재노드를 방문처리
    visited[start] = True
    #큐가 빌때 까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v =queue.popleft()
        print(v,end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]= True

#각 노드가 연결된 정보를 리스트 자료형으로 표현
graph =[
    [],  # 0번노드는 없으니깐 ㅋ
    [2, 3, 8],  # 1번노드
    [1, 7],  # 2번노드
    [1, 4, 5],  # 3번노드 연결된 값들
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

#각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원리스트)
visited = [False]*9
#정의된 BFS 함수 호출
bfs(graph, 1, visited)

결과

 

1 2 3 8 7 4 5 6 

 

* 노드의 방문순서가 DFS 탐색 결과와 다르다..!

* DFS 는 재귀호출을 통해 방문처리했다면, BFS 는 queue.popleft() 를 통해 먼저들어온값 순으로 방문처리

 깊이우선탐색 DFS 보다 빠르다라는 점 알아두자