[알고리즘] BFS / DFS

모든 간선(edge)의 비용이 동일할 때는 BFS 사용하기

너비우선탐색 (Breadth First Search)

노드들과 같은 레벨에 있는 노드들(형제노드)을 먼저 탐색하는 방식

• 파이썬에서 제공하는 딕셔너리와 리스트를 활용해서 그래프를 표현할 수 있음
• BFS 방식: A - B - C - D - G - H - I - E - F - J

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):
    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

로직

1. 먼저 탐색할 노드를 start_node로 지정하고, need_visit 리스트에 넣음
   (while 무한반복)
2. need_visit 리스트의 첫번째 노드를 꺼내고, need_visited 리스트에서 삭제함
3. visited 리스트에 없으면, 노드를 리스트에 추가하고, 해당 key의 value를 need_visit 리스트에 추가함
4. 다 끝나면, visited 리스트를 출력함

시간 복잡도

O(V+E)

(알고리즘에서 while문을 V + E 번 만큼 수행함)

• V : 노드 수
• E : 간선 수

깊이우선탐색 (Depth First Search)

노드의 자식들을 먼저 탐색하는 방식

• DFS 방식: A - B - D - E - F - C - G - H - I - J
• 코드로 구현할 때, need_visit 리스트는 스택 자료구조를 사용한다.
• 좌, 우 중 어느 방향으로 진행하든 상관 없음
• BFS는 pop(0) / DFS는 pop()

코드

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

로직

1. 먼저 탐색할 노드를 start_node로 지정하고, need_visit 리스트에 넣음
   (while 무한반복)
2. need_visit 리스트의 마지막 노드를 꺼내고, need_visited 리스트에서 삭제함
3. visited 리스트에 없으면, 노드를 리스트에 추가하고, 해당 key의 value를 need_visit 리스트에 추가함
4. 다 끝나면, visited 리스트를 출력함

시간 복잡도

O(V+E)