[BFS] 너비우선탐색 (Breath-First Search)

BFS란? by Queue

Breath-First Search의 약자로 너비우선탐색을 의미한다.

시작노드에서 가장 가까운 노드부터 탐색하는 것을 말한다.

이를 구현하기 위해선 큐의 자료구조가 사용된다. 

 

전제조건은 노드 숫자가 가장 낮은 노드부터 시작한다고 생각하자. 

1. 시작 노드 : 1 

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

3. 이제 2를 꺼내서 방문처리 후, 1과 7 중 방문하지 않는 7을 넣고 방문처리한다. 

4. 3을 꺼내서 방문처리 후, 3과 인접한 노드 1, 4, 5 중 방문하지 않는 4 5를 큐에 넣는다. 

5. 8을 꺼내서 방문처리 후, 8과 인접한 노드가 없으므로 큐에 넣지 않는다. 

6. 7을 꺼내서 방문처리 후, 7과 인접한 노드 2,8,6 중 방문하지 않은 노드 6을 큐에 넣는다.

7. 4를 꺼내서 방문처리 후, 인접한 노드가 모두 방문했으므로 큐에 넣지 않는다.

8. 5를 꺼내서 방문처리

9. 6을 꺼내서 방문처리 

따라서, 전체 노드 탐색 순서는  

1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

 

이를 정리하자면,

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

BFS구현 

# 각 노드가 연결된 정보를 표현 
# 0번노드는 없으니깐 빈리스트
# 1번노드에 연결된 노드는 2, 3, 8

graph = [
    [],
    [2, 3, 8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 노드 표현 
# >> 우선 모든 노드는 방문하지 않은 것처럼 
visited = [False] * 9
print(visited)

>>> [False, False, False, False, False, False, False, False, False]

from collections import deque

# 필요인자 : 그래프, 시작노드, 방문처리리스트
def bfs(graph, start, visited):
    # queue는 큐 자료구조 1을 넣고 방문처리 
    queue = deque([start])
    visited[start] = True
    
    # 큐 안에 
    while queue:
        # 큐 안에 있는 것을 빼고 방문처리. 
        # >> 1
        v = queue.popleft()
        print(v, end=' ')
        # 노드1번에 인접한 노드 2,3,8 중 방문하지 않았다면 큐에 넣고 방문처리
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

#정의된 DFS 함수 호출
bfs(graph, 1, visited)

>>> 1 2 3 8 7 4 5 6

 

 

참고문헌

이것이 취업을 위한 코딩테스트다 동영상을 공부하고 TIL입니다