DFS/BFS (Depth-First Search / Breadth-Frist Search)

DFS (Depth - First Search)

• 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 (Stack) 을 사용하여 표현

동작과정

1. 탐색 시작 노드를 스택에 push하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리
    - 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 위의 과정을 더 이상 수행할 수 없을 때까지 반복 

코드 구현

graph = {
    1: [2, 5, 9],
    2: [3],
    3: [4],
    4: [],
    5: [6, 8],
    6: [7],
    7: [],
    8: [],
    9: [10],
    10: []
}

def recursive_dfs(v, visited = []):
    visited.append(v)  # 시작 정점 방문
    
    for W in graph[v]:
        if not w in visited:  # 방문하지 않았으면
            visited = recursive_dfs(w, visited)
    
    return visited
    
def iterative_dfs(start_v):
    visited = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)
    
    return visited
    
print("recursive_dfs: ", recursive_dfs(1))
print("iterative_dfs: ", iterative_dfs(1))

# 스택은 마지막에 스택에 담은 정점부터 꺼내져 방문되기 때문에
# 재귀 방식과 결과가 다름
#==============================

recursive_dfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
iterative_dfs: [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]

출처 : https://devyuseon.github.io/algorithm/dfs-and-bfs/#%EA%B0%84%EB%8B%A8-%EA%B0%9C%EB%85%90-1

---

BFS (Breadth-First Search)

• 너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘
• 가장 가까운 노드부터 우선 순위로 하기에 큐 (Queue)를 사용하여 표현
• Python에는 collections의 deque 라이브러리를 통해 큐를 사용 가능
   - 큐를 list로 사용하여 입력 = list.append(), 출력 = list.pop()으로 구현 가능
   - 하지만, 시간복잡도가 O(N)이라 비효율적일 수 있음
• 일반적으로 DFS보다 수행 시간이 좋음

동작과정

1. 탐색 시작 노드를 큐에 삽입 후 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
    - set을 사용하면 쉽게 구현 가능
3. 위의 과정을 더 이상 수행할 수 없을 때까지 반복

코드구현

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [6, 7],
    4: [8],
    5: [9],
    6: [10],
    7: [],
    8: [],
    9: [],
    10: []
}

def bfs(start_v):
    visited = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                queue.append(w)
                
    return visited
    
print("bfs: ", bfs(1))

#==============================

bfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

Deque를 사용한 코드

from collections import deque

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