[알고리즘] DFS, BFS

 

1. DFS (depth first search)

 

맹목적 탐색 기법 중 하나로, 자식 노드를 확장할 수 있을때까지 깊이 우선으로 탐색을 진행하는 방법

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

 

재귀적 DFS

def recursive_dfs(graph, v, discovered=[]):
    discovered.append(v)  # 방문한 노드 기록
    for w in graph[v]:
        # 현재 방문한 노드와 연결되어 있는 노드 (w)
        if w not in discovered:
            # w가 방문되지 않았을 경우에 아래 실행
            discovered = recursive_dfs(graph, w, discovered)
    return discovered

 

Stack 이용한 DFS

def iterative_dfs(graph, start_v, discovered):
    stack = [start_v]  # stack : last in first out (LIFO)
    while stack:
        v = stack.pop()
        print(v)
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    return discovered

 

DFS에서 추가적으로 알아야 하는 개념이 있는데, 그것은 바로 백트래킹(backtracking)이다.깊이우선으로 탐색을 진행하다 찾고자 하는 해와는 거리가 멀어질 경우 왔던 경로로 되돌아가는 방법을 말한다.이처럼 탐색을 진행하다가 가능성이 없다고 판단될 경우 backtracking을 진행하는 것을 가지치기(pruning)이라고 한다.

 

이러한 backtracking은 제약 충족 문제에서 필수적으로 사용된다.game tree search 등 최적해를 찾아나가는 과정에서 깊이제한으로 탐색을 진행하게 되면 시간 조건을 충족하지 못하기 때문에깊이 제한이나 다른 제약 조건을 걸어 backtracking을 진행하곤 한다.

 

---

2. BFS(breadth first search)

 

맹목적 탐색 기법 중 하나로, 동일 level에 존재하는 node를 탐색한 후 다음 level을 탐색하는 기법

 

Queue이용한 BFS

def iterative_bfs(graph, start_v):
    discovered = []
    queue = deque()
    queue.append(start_v)

    while queue:
        node = queue.popleft()
        if node not in discovered:
            discovered.append(node)
            for child_node in graph[node]:
                queue.append(child_node)
    return discovered

 

재귀를 이용하여 BFS를 구현할 수 없다.