알고리즘: DFS와 BFS

그래프 탐색 방법

그래프를 탐색하는 방법중 DFS(Depth First Search와 BFS(Breadth First Search)를 간단한 예시를 통해 이해하고자 한다. 두 방식은 각각 Stack과 Queue를 통해 구현할 수 있으며, 그래프 방문 여부를 체크하여 중복으로 탐색하는 것을 방지하여야 한다.

 

그래프를 코드로 나타내기

Figure 1. 그래프 예시

그림 1의 그래프에 대한 노드 정보를 코드로 나타내면 다음과 같다.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E', 'F'],
    'D': ['B', 'G'],
    'E': ['C', 'H'],
    'F': ['C'],
    'G': ['D'],
    'H': ['E'],
}

---

DFS

Figure 2. Figure 1의 그래프 DFS 탐색 과정

그림 2는 루트 노드를 시작으로 모든 그래프 경로를 탐색하는 과정이다.

1. 루트 노트인 A를 Stack에 push 하고 visited로 표시 한다.
2. A를 pop하고 A의 자식노드인 B C를 순서대로 stack에 push 한다.
3. Stack은 LIFO이므로 그림과 같이 top 위치에 있는 노드들이 우선적으로 탐색되게 된다.
4. 따라서 DFS는 시작 노드를 시작으로 깊이 우선으로 그래프를 탐색할 수 있다.

BFS

BFS는 DFS와 달리 FIFO로 처리한다. 따라서 DFS와 다른점은 Stack을 사용하는 것이 아닌 Queue를 사용한다고 생각하면 쉽다.

 

Code

def sfs(graph, start, select):
    visited = {}
    lst = []

    lst.append(start)

    while lst:
        if select == 'DFS':
            node = lst.pop()
        else:
            node = lst.pop(0)

        if node not in visited:
            visited[node] = True
            lst.extend(graph[node])
    return visited.keys()

• 앞서 언급하였듯이 DFS와 BFS는 사용하는 Stack을 사용하여 LIFO로 처리하냐 Queue를 사용하여 FIFO로 처리하느냐에 따른 방법의 차이이다.
• DFS는 While과 stack을 통해 구현할 수도 있고, 재귀 호출을 통해 구현할 수도 있다.
• 두 방식의 차이를 쉽게 이해하기 위해 select first sort라는 함수를 구현하였다.