[모각코 8주차] 알고리즘 DFS, BFS

깊이 우선 탐색 (DFS, Depth-First Search)

최대한 깊이 내려간 뒤, 더 이상 갈 곳이 없을 경우 옆으로 이동

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에해당 분기를 완벽하게 탐색하는 방식

 

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다좀 더 간단

3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서느림

 

 

너비 우선 탐색 (BFS, Breadth-First Search)

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

 

 

루트 노드(혹은 다른 임의의 노드)에서 시작해서인접한 노드를 먼저탐색하는 방법으로,시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

 

1. 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택함

 

DFS / BFS 비교

사용하는 문제 유형

• 그래프의 모든 정점을 방문하는 것이 주요한 문제
  • DFS / BFS 모두 사용 가능

• 경로의 특징을 저장해둬야하는 문제
  • DFS

• 최단거리를 구해야 하는 문제
  • BFS

• 그 외,
  • 검색 대상 그래프가 크다면 DFS
  • 규모가 크지 않고 원하는 대상이 멀지 않다면 BFS

Code (Python)

def dfs(start, visited = []):
    visited.append(start)
    for child in graph[start]:
        if child not in visited:
            visited = dfs(child, visited)
    return visited

def bfs(start):
    visited = [start]
    deq = deque()
    deq.append(start)
    while deq:
        v = deq.popleft()
        for child in graph[v]:
            if child not in visited:
                visited.append(child)
                deq.append(child)
    return visited