[알고리즘] DFS, BFS 구현 (Python)

DFS

"""
       1
    /  |  \
   2   3   4
   |   |
   5   |
  / \ /
 6   7
"""
 
graph = {
    1: [2,3,4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7],
    6: [],
    7: [3],
}
 
def recursive_dfs(v, discovered = []):
    discovered.append(v) # 시작 정점 방문
    for w in graph[v]:
        if not w in discovered: # 방문 하지 않았으면
            discovered = recursive_dfs(w, discovered)
    return discovered
 
def iterative_dfs(start_v):
    discovered = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    return discovered
 
print("recursive_dfs: ", recursive_dfs(1))
print("iterative_dfs: ", iterative_dfs(1))
 
# 스택은 마지막에 스택에 담은 정점부터 꺼내져 방문되기 때문에 재귀 방식과 결과가 다름.

BFS

"""
       1
    /  |  \
   2   3   4
   |   |
   5   |
  / \ /
 6   7
"""
 
graph = {
    1: [2,3,4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7],
    6: [],
    7: [3],
}
 
def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop()
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered
 
print("iterative_bfs: ", iterative_bfs(1))
 
"""
iterative_bfs:  [1, 2, 3, 4, 5, 6, 7]
"""

 

DFS는 Stack, BFS는 Queue로 구현한다.

 

dfs, bfs 헷갈릴 때 마다

 

이분 영상 본다.

bfs, dfs말고도 알고리즘이나 자료구조 설명이 알기 쉽게 잘 되어있다.