그래프 탐색 : 하나의 정점을 시작으로 그래프의 모든 정점을 탐색. (그래프는 배열 처럼 정렬되어 있지 않기 때문에 모두 방문 필요)

그래프 탐색 방법 : BFS & DFS

BFS (Breathed First Search) : 너비 우선 탐색

• 지정 노드(루트 또는 임의의 노드)로부터 가까운 정점부터 검색.

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

• Queue를 이용해서 구현

장점 : 최단 길이 경로 보장.

단점 : 최악의 경우 모든 경로를 확인 필요. (목표가 깊을 수록 오랜 시간 소요)

DFS (Depth Fist Search) : 깊이 우선 탐색

• 하나의 경로를 끝까지 탐색 한 후, 찾으려는 목표가 아니라면 다음 경로로 넘어가 탐색.

• Stack 또는 Recursion 함수를 이용해 구현

• 방문한 노드를 표현해야한다. 그렇지 않으면 무한루프에 빠지게 된다.

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

단점 : 최단 경로 보장 안됨.

BFS vs DFS

• BFS : 그래프가 큰 경우, 최단거리 문제

• DFS : 그래프의 규모가 작고, depth가 얕은 경우, 이동한 정점의 값을 가지고 계속 연산을 하는 경우(재귀적으로 호출되는경우)