자료구조 - 탐색알고리즘 BFS

BFS

Breath First Search  알고리즘은 너비우선 알고리즘 이라고도 하는데

DFS는 가장 멀리 있는 노드부터 탐색한다면 BFS는 그반대다.

가장 가까운 노드 부터 탐색 한다.

 

이러한 알고리즘의 구현에는 먼저 들어간 노드를 자료구조에 넣고 탐색하고 

이후 해당 인접노드를 가까운 곳부터 노드에 넣고 탐색해야하므로

먼저들어간 노드가 없어진다음 그 다음 노드가 탐색되어야 한다.

 

선입선출의 알고리즘 즉, 큐 자료구조로 구현해야한다.

 

BFS

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

2. 큐에서 노드를 꺼내고 해당 노드의 인접노드들을 큐에 넣고 방문처리한다.

3. 2번을 끝까지 반복한다.

 

1. 시작 노드 1을 큐에 삽입하고 방문처리 한다.

2. 노드 1을 큐에서 꺼내고 방문하지 않은 인접 노드 2, 5를 큐에 넣고 방문처리한다.

3. 노드 2를 큐에서 꺼내고 방문하지 않은 인접노드 3을 큐에 넣고 방문처리한다.

4. 노드 5을 큐에서 꺼내고 방문하지 않은 인접노드 4를 큐에 넣고 방문처리한다.

5. 노드 3을 큐에서 꺼내고 방문하지 않은 인접노드가 없으므로 넘어간다.

6. 노드 4를 큐에서 꺼내고 방문하지 않은 인접노드 6을 큐에 넣고 방문처리한다.

7. 노드 6을 큐에서 꺼내고 방문하지 않은 인접노드가 없으므로 종료한다.

 

이를 파이썬으로 구현하면

from collections import deque

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 = [
    [],
    [2, 5],
    [1, 3, 5],
    [2, 4],
    [3, 5, 6],
    [1, 2, 4],
    [4]
]

visited = [False] * 9

bfs(graph, 1, visited)

 위와 같다. 

 

잠깐 deque 선언에 대해 설명하면

# 빈 큐 만들기

deque1 = deque()

# 원소가 있는 큐 만들기

deque2 = deque([1, 2, 3])

# 큐 최대 길이 명시하기(원소를 이보다 많이 넣으면 maxlen이 자동 갱신됨)

deque3 = deque(maxlen=5)

 

BFS 코드 설명

1. bfs를 구현하기 위해 deque 자료구조를 사용하며

2. queue가 빈다면 False( -1)를 반납하므로 while queue:

3. 큐에서 노드를 꺼내고 해당 노드의 인접노드들이 방문을 하지 않았다면 

4. 큐에 넣고 방문처리를 한다.