잔재미코딩

너비 우선 탐색 (BFS)

처음하는 파이썬 데이터 분석

혹시 본 자료가 도움이 되셨다면, 이런식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 데이터 분석

전처리, pandas, 시각화까지 전과정을 까지 짧은 시간에 견고하게 정리하기

자세히 알아보기 모든 강좌 보기

3. 너비 우선 탐색 (Breadth-First Search)

1. BFS 와 DFS 란?

  • 대표적인 그래프 탐색 알고리즘
    • 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
    • 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

BFS/DFS 방식 이해를 위한 예제

  • BFS 방식: A - B - C - D - G - H - I - E - F - J
    • 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함
  • DFS 방식: A - B - D - E - F - C - G - H - I - J
    • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

2. 파이썬으로 그래프를 표현하는 방법

  • 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음

그래프 예와 파이썬 표현

In [4]:
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']
처음하는 파이썬 데이터 분석

혹시 본 자료가 도움이 되셨다면, 이런식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 데이터 분석

전처리, pandas, 시각화까지 전과정을 까지 짧은 시간에 견고하게 정리하기

자세히 알아보기 모든 강좌 보기
In [5]:
graph
Out[5]:
{'A': ['B', 'C'],
 'B': ['A', 'D'],
 'C': ['A', 'G', 'H', 'I'],
 'D': ['B', 'E', 'F'],
 'E': ['D'],
 'F': ['D'],
 'G': ['C'],
 'H': ['C'],
 'I': ['C', 'J'],
 'J': ['I']}

3. BFS 알고리즘 구현

  • 자료구조 큐를 활용함
    • need_visit 큐와 visited 큐, 두 개의 큐를 생성

  • 큐의 구현은 간단히 파이썬 리스트를 활용
In [9]:
data = [1, 2, 3]
data.extend([4, 5])
data
Out[9]:
[1, 2, 3, 4, 5]
In [12]:
def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited
In [13]:
bfs(graph, 'A')
Out[13]:
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

처음하는 파이썬 데이터 분석

혹시 본 자료가 도움이 되셨다면, 이런식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 데이터 분석

전처리, pandas, 시각화까지 전과정을 까지 짧은 시간에 견고하게 정리하기

자세히 알아보기 모든 강좌 보기

4. 시간 복잡도

  • 일반적인 BFS 시간 복잡도
    • 노드 수: V
    • 간선 수: E
      • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
    • 시간 복잡도: O(V + E)
In [15]:
def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    count = 0
    while need_visit:
        count += 1
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    print (count)
    return visited
In [16]:
bfs(graph, 'A')

19
Out[16]:
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

깊이 우선 탐색 (DFS) 탐욕 알고리즘의 이해