그래프 탐색 알고리즘

개요

그래프는 여러 관계를 나타내는데 적합한 데이터구조입니다. 예를 들어, SNS상의 친구 관계도를 그리면 그래프 구조를 가질 것입니다.

그렇다면 그래프 상에서 특정 Node을 탐색하기 위해서는 어떻게 해야할까요?
그래프 탐색 알고리즘 2개(BFS, DFS)에 관해 알아보겠습니다.

Breadth-First-Search

BFS 알고리즘은 너비 탐색 알고리즘으로, 아래 gif과 같이 탐색합니다.

이를 알고리즘으로 구현하기 위해서 queue 구조와 hashtable을 사용합니다. queue구조에는 다음에 방문할 노드들을 집어넣고, hashtable에는 특정 노드를 방문했는지, 안했는지를 기록합니다.

자세한 구현 원리는 생략하겠습니다.(어떻게 구현할지 머릿속으로 그려보세요!)

출처: https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

Depth-First -Search

DFS 알고리즘은 깊이 탐색 알고리즘으로, 아래 gif과 같이 탐색합니다.

이를 알고리즘으로 구현하기 위해서는 stack 구조와 hashtable을 사용합니다. stack구조에는 다음에 방문할 노드들을 집어넣고, hashtable에는 특정 노드를 방문했는지, 안했는지를 기록합니다.

출처: https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif