[알고리즘] 너비 우선 탐색 (Breadth-First Search) 과 깊이 우선 탐색 (Depth-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. 파이썬으로 그래프를 표현하는 방법

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

그래프 예와 파이썬 표현

g = dict()
g['A'] = ['B', 'C']
g['B'] = ['A', 'D']
g['C'] = ['A', 'G', 'H', 'I']
g['D'] = ['B', 'E', 'F']
g['E'] = ['D']
g['F'] = ['D']
g['G'] = ['C']
g['H'] = ['C']
g['I'] = ['C', 'J']
g['J'] = ['I']

print(g['A']) # ['B', 'C']

3. BFS 알고리즘 구현

• 자료구조 큐를 활용함
  - need_visit 큐와 visited 큐, 두 개의 큐를 생성
  
• 큐의 구현은 간단히 파이썬 리스트를 활용

def bfs(g, startNode):
    visited = list()
    needVisit = list()
    
    needVisit.append(startNode)
    
    while needVisit:
        node = needVisit.pop(0)
        if node not in visited:
            visited.append(node)
            needVisit.extend(g[node]) # 자식 노드를 이어붙이기
    
    return visited

bfs(g, 'A') # ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

파이썬 문법: pop() 과 extend()

pop()

data = [1,2,3]
data.pop(0) # 만약 인자 없이 data.pop() 을 한다면, 맨 뒤 원소를 pop 하고 [1,2] 만 남음
print(data) # [2, 3]

extend()

data = [1,2,3]
data.extend([4,5]) # 리스트에 리스트 이어붙이기
print(data) # [1, 2, 3, 4, 5]

4. DFS 알고리즘 구현

DFS 의 구현은 앞서 구현했던 BFS 와 유사하다.
needVisit 의 자료구조를 ‘큐’가 아닌 ‘스택’을 이용하면 된다!

def dfs(g, startNode):
    visited = list()
    needVisit = list()
    
    needVisit.append(startNode)
    
    while needVisit:
        node = needVisit.pop() # 🌟 pop() 에 인자가 없으면 맨 마지막 데이터 추출 (stack 과 마찬가지)
        if node not in visited:
            visited.append(node)
            needVisit.extend(g[node])
            
    return visited

dfs(g, 'A') # ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']

5. BFS 와 DFS 의 시간 복잡도

BFS 와 DFS 의 시간 복잡도는 같다.

• 노드 수: V
• 간선 수: E
  - 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
• 시간 복잡도: $O(V + E)$

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기