[Algorithm] 19강 : BFS(너비 우선 탐색) 알고리즘 정의와 예제

BFS란?

 

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

BFS는 큐 자료구조를 이용

 

 

동작과정

 

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

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

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

 

 

 

동작 예시

 

 시작 노드를 1로 정하고 근접한 노드를 찾는다. 이때 방문 기준은 번호가 낮은 인접 노드부터이다. 

 

이때 1에 따라서 2,3,8 이 생긴다. 이걸 큐에 넣고 방문 처리한다.

 

그다음은 인접했던 값 중에 제일 작았던 2에 대해 인접 노드를 추가해준다. 그전에 있던 1은 사라지고 2와 인접한 노드를 추가해준다. 그래서 3,8,7 이 남는다. 

 

이런 식으로 모든 노드에 대해 탐색을 한다. 

이 과정을 반복하면 탐색 순서는 위와 같이 된다.

 

 

BFS 소스 코드 예제

from collections import deque

#BFS 메서드 정의
def bfs(graph,start,visited):
	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
                
 # 각 노드가 연결된 정보를 표현(2차원 리스트)
 graph =[
 	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [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

 

---

www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.

 

출처: https://continuous-development.tistory.com/170?category=736684 [나무늘보의 개발 블로그]