[Algorithm] BFS & DFS

그래프 순회

그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정

• 깊이 우선 탐색(Depth-First Search)
  • 스택 또는 재귀로 구현
  • 미로찾기를 풀기 위한 전략을 찾다가 고안
• 너비 우선 탐색(Breadth-First Search)
  • 주로 큐로 구현
  • 그래프의 최단 경로를 구하는 문제 등에 사용

그래프 표현 방법

• 인접 행렬(Adjacency Matrix)
• 인접 리스트(Adjacency List)

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

DFS(깊이 우선 탐색)

• recursive_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

• stack : iterative_dfs

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

BFS(너비 우선 탐색)

def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]

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

    return discovered