[Python] DFS(재귀/반복), BFS 구현

본 내용은 <파이썬 알고리즘 인터뷰>를 참고했습니다.

재귀 DFS

def recursive_dfs(v, discovered = []):
    discovered.append(v)
    for w in graph[v]:
        if w not in discovered:
            discovered = recursive_dfs(w, discovered)
    return discovered

스택을 이용한 반복 DFS

def iterative_dfs(start_v):
    discoverd = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            for w in graph[v]:
                stack.append(w)
    return discovered

큐를 이용한 반복 BFS

def iterative_bsf(start_v):
    discovered = []
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in discoverd:
                discoverd.append(w)
                queue.append(w)
    return discoverd