그래프 탐색 알고리즘 [DFS, BFS]

프로그래밍에 자주 사용되는 대표적인 자료구조에는 "그래프"가 있습니다. 

오늘 포스팅에서는 그래프를 탐색하는 알고리즘 2가지 DFS와 BFS에 대해서 알아보도록 하겠습니다.

그래프는 정점과 간선으로 이루어져 있는데 간선을 통해서 모든 정점을 방문하는 것을 그래프를 탐색한다고 합니다.

위에서 언급했듯이 그래프 탐색 알고리즘에는 대표적으로 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 있습니다. 각각의 알고리즘에 대해서 자세히 알아보도록 하겠습니다.

위 그림을 보시면 두 알고리즘의 차이에 대해서 직관적으로 이해하실 수 있습니다. 각 알고리즘의 명칭에서도 볼 수 있듯이 깊이(자식)를 우선으로 탐색하느냐 아니면 너비(형제)를 우선으로 탐색하느냐의 차이가 있습니다.

1. 깊이 우선 탐색

---

깊이 우선 탐색 (Depth First Search)은 트리 혹은 그래프에서 노드의 자식들을 우선으로 탐색하는, 즉 최대한 깊숙히 탐색한 후 다시 돌아가 다른 루트를 탐색하는 방법입니다. 여기서 한 노드에서 제일 마지막 자식까지 탐색을 마치고 돌아오는 과정을 백트리킹(Backtracking)이라고 합니다. 구현에는 주로 스택 자료구조를 사용합니다.

 
# Python implementation of DFS using stack
def dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

#======================================#

# DFS using recursion
class Node:
    def __init__(self, data):
        self,data = data
        self.child = []
        self.visited = False

def dfs(A):
    if A.visited == True:
        return
    
    print(A.data)
    a.visited = True
    for child in node.childs:
        dfs(child)

2. 너비 우선 탐색

---

너비 우선 탐색 (Breadth First Search)은 트리 혹은 그래프에서 노드의 인접한 모든 정점들을 우선으로 탐색하는 방법입니다. 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장하는 방법입니다. 구현에는 주로 큐 자료구조를 사용합니다.

 
# Python implementation of BFS using queue
def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        n = queue.pop(0)
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited

정말 쉽게 설명해주시는 유튜브 영상도 첨부하겠습니다. 포스팅 내용이 너무 빈약하기 때문에 아래 영상을 참조하시면 더욱 쉽고 더욱 깊은 내용을 공부할 수 있습니다.

출처

• http://ejklike.github.io/2018/01/05/bfs-and-dfs.html
• http://mishadoff.com/blog/dfs-on-binary-tree-array/
• https://m.blog.naver.com/PostView.nhn?blogId=complusblog&logNo=221155195082&proxyReferer=https%3A%2F%2Fwww.google.com%2F