[알고리즘 개념] BFS

BFS(Breadth-First Search) 에 대해 알아보겠습니다.

 

앞서 공부한 DFS와는 어떤 차이가 있는지 비교해보겠습니다.

BFS	DFS
탐색 방식 : BFS는 시작 노드에서 출발해 인접 노드를 모두 탐색 후 다음 인접 노드를 탐색 자료구조 : 큐/queue를 주로 사용합니다. 경로탐색: 최단 경로를 찾는데 유리합니다. 모든 간선의 가중치가 동일하면, BFS는 최단 경로를 보장	탐색방식: 시작 노드에서 출발하여 한 노드의 인접노드를 탐색하고 그 노드의 인접 노드를 탐색하며 깊이 우선으로 탐색 자료구조 :Stack 또는 재귀호출을 사용하여 구현 경로 탐색: 특정 경로를 탐색하거나 연결 요소를 찾는데 유리합니다. 특정 상황에서는 최단 경로를 보장하지 않습니다.

 

BFS는 시작 노드에서 출발해 인접 노드를 모두 탐색 후 다음 인접 노드를 탐색

 

 

BFS 구현 순서는 다음과 같습니다.

1. 큐를 초기화 합니다.

queue에 처음 시작 노드를 넣습니다.

가장 왼쪽에 있는 queue를 꺼내고 방문처리합니다.

해당 노드와 인접해있는 노드들 중 방문처리 되지 않은 노드를 다시 큐에 추가(append)합니다.

 

2. 큐가 빌때까지 반복합니다.

 

 

python 코드로 구현해보기

 

deque를 선언합니다.

from collections import deque

 

그래프를 설정하고, 시작 노드를 설정합니다. 파이썬 데이터 타입인 set을 사용하면 쉽게 구현이 가능합니다.

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1

 

1.visited[]- 방문처리

2.queue에 root값 넣기

3.queue가 빌때까지 반복

4.queue의 가장 왼쪽에 있는 노드 꺼내기popleft()

5.방문하지 않았다면

6. 방문처리하기

7.queue값에 방문하지 않은 인접노드 추가로 넣기

8.visited list return 하기

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited

 

 

참고자료 출처

https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html

[Daily PS] 파이썬으로 구현하는 BFS와 DFS