자료구조 Graph traversal

그래프 탐색은 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적

그래프의 데이터는 배열처럼 정렬이 되어 있지 않기 때문에 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.

경로를 탐색할 때 최단 경로나 최소 환승 등 하나의 목적에도 여러 가지 방법 있듯이

가장 대표적인 두 가지 방법, DFS와 BFS.

(탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같음)

각 장단점에 맞춰 상황에 맞는 탐색 기법을 사용해야함

 

BFS(Breadth-First Search)

한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색

더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문

너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색

주로 두 정점 사이의 최단 경로를 찾을 때 사용

 

 

DFS(Depth-First Search)

비행기 티켓이 없다면 어떤 비행기가 미국으로 가는 것인지 알 수 없음.

이때 비행기를 타고 여러 나라를 방문하면서, 마지막에 미국에 도착하는 경로를 찾아야.

하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색

하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가

깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색

한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용.

BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색

 

 

출처 : 코드스테이츠