[이론] DFS, BFS

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

• Stack(OR 재귀)로 구현

# 첫번째: 스택에 넣고 방문처리하기
# 두번째부터: 스택에 있는 것 하나 빼서 방문하지 않은 것이 있으면, 스택에 넣고 방문처리하기
def dfs(graph, vertex, visited):
    visited[vertex] = True # 스택에 넣고 방문처리하기
    print(vertex, end=' ')
    for i in graph[vertex]: # 스택에 있는 것 하나 빼서
        if visited[i] == False: # 방문하지 않은 것이 있으면
            dfs(graph, i, visited) # (재귀)

 

BFS(Breath-First Search): 너비 우선 탐색

• Queue로 구현

from collections import deque
queue = deque()

# 첫번째: 큐에 넣고 방문처리하기
# 두번째부터: 큐에 있는 것 하나 빼서 방문하지 않은 것 있으면, 🖐🏼모두🖐🏼 큐에 넣고 방문처리하기
def bfs(graph, vertex, visited):
    queue.append(vertex) # 큐에 넣고
    visited[vertex] = True # 방문처리하기
    print(vertex, end=' ')

    while queue:
        for i in graph[queue.popleft()]: # 큐에 있는 것 하나 빼서 (🖐🏼모두🖐🏼)
            if visited[i] == False: # 방문하지 않은 것이 있으면,
                queue.append(i) # 큐에 넣고
                visited[i] = True # 방문처리하기
                print(i, end=' ')

 

비교분석

실제 구현된 것을 보면 왜 Depth 우선인지, Breath 우선인지 알 수 있음.

Depth 우선: for 문 내에서 한 원소에 대해 바로 스택에 넣고 / 스택에서 빼기

Breath 우선: for문 다 돌면서 모든 원소에 대해 큐에 넣고 / 큐에서 빼기

 

DFS: for 문  1) 내의 재귀함수

BFS: for 문 1) 을 감싸는 while문과 2) 내의 코드의 반복