[Algorithm] BFS(Breadth-first search,너비 우선 탐색)

BFS란?

 

시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 두 노드사이의 최단경로를 탐색할때 활용하기 좋은 방식이다. 주로 queue을 사용하여 구현한다.

 

 

BFS의 특징

• 해당 노드 주변을 먼저 탐색
• 두 노드 사이의 최단거리를 찾을 때 BFS
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함

큐를 이용한 BFS 동작과정

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

예제 그래프

위의 과정대로 진행하면 1 2 3 8 7 4 5 6 순으로 노드를 탐색하게 된다.

일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.

 

구현 코드

from collections import deque

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
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)