넓이 우선 탐색을 위한 파이썬 알고리즘 BFS

깊이 우선 탐색을 위한 파이썬 알고리즘 DFS

지난번에는 DFS 깊이우선탐색을 해보았는데 바로 이어서 BFS 넓이우선탐색을 해보겠습니다.

탐색 방법은 다음과 같다.

루트에서 시작한다.

자식 노드들을 [1]에 저장한다.

[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.

[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.

위의 과정을 반복한다.

모든 노드를 방문하면 탐색을 마친다.

DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다.

앞서 DFS는 재귀나 스택으로 구현을 했는데 BFS는 큐로 구현을 합니다.

def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:    
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

가장먼저 시작점을 discovred에다가 집어넣고 이어서 queue에다가 시작점을 넣고 시작을 합시다.

그런다음 처음으로 들어온 시작점을 빼고 그 시작접에서 갈 수 있는 곳들을 discovered와 queue에 집어넣어 줍시다.

그리고 queue에서 첫번째로 들어온 값을 뺀다음 그 값에서 갈 수 있는 곳을 쭉 찾고 이 과정을 반복합니다.

그래프는 지난번 DFS다룰때 사용한 것과 같습니다. 참고로 BFS는 재귀로 작동하지 않습니다.