BFS-Python(파이썬)

BFS 개념

그래프 자료 구조에서 원하는 자료를 찾는 탐색 알고리즘

수평 방향으로 원하는 노드를 탐색하는 알고리즘이다.

그림과 같이 수평 방향으로 노드들을 탐색한다.

 

BFS 구현 원리

BFS의 핵심은 "방문하고자 하는 노드"와 "방문했던 노드"를 나누어서 구성하는 것이 핵심이다.

 

먼저 시작 노드를 방문했던 노드에 삽입한다

 

그 후 방문할 노드에 시작 노드의 자식 노드를 삽입한다.

 

마지막으로 자식 노드 중심으로 1~2단계를 거쳐 탐색한다.

 

BFS 구현

기반 데이터(위의 그림과 같은 그래프이다.)

 

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

 

코드

def bfs(graph, start_node):
    need_visited, visited = list(), list()
    need_visited.append(start_node)
    while need_visited:
        node = need_visited.pop(0)
        if node not in visited:
            visited.append(node)

            need_visited.extend(graph[node])
            
    return visited

 

BFS의 경우 DFS와 차이가 pop함수 부분밖에 없다. 이는 while문에서 어떤 자료를 우선적으로 추출하느냐의 차이정도 밖에 없기 때문이다.

 

DFS의 경우 리스트의 가장 끝에 있는 데이터를 기준으로 추출하는 반면에, DFS는 리스트의 가장 처음에 있는 데이터를 기준으로 인자를 받기 때문이다.

 

이 코드의 경우도 역시 pop(0)의 경우 시간 복잡도가 O(n)이기에 좋지 않다.

 

다음은 deque를 활용한 코드이다.

 

from collections import deque

def bfs(graph,start_node):
    visited=list()
    need_visited=deque()
    need_visited.append(start_node)
    while need_visited:
        node=need_visited.popleft()
        if node not in visited:
            visited.append(node)
            if node not in graph:
                return visited
            need_visited.extend(graph[node])
    return visited

 

알고리즘을 살펴 보면 결국

 

먼저 시작 노드를 큐에 추가, 큐에 추가한 노드를 꺼내고, 자식 노드들을 다시 큐에 추가, 큐에서 다시 제일 아래 있는 것을 꺼내서 출력하고..... 이 과정을 반복해서 출력된 결과값이 BFS라고 보면 된다.

 

참고 유튜브 사이트:

https://www.youtube.com/watch?v=_hxFgg7TLZQ&t=288s&ab_channel=%EC%97%94%EC%A7%80%EB%8B%88%EC%96%B4%EB%8C%80%ED%95%9C%EB%AF%BC%EA%B5%AD 

 

제일 확실한 것은 어떤 그래프를 보고 BFS로 탐색시 어떤 결과가 나오는지 생각하고 코드를 이해하는게 중요한 것 같다.