[Data Structure] 그래프 탐색

그래프 탐색 방법

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

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

• DFS ≒ 전위/중위/후위 순회
• BFS ≒ 레벨 순회

 

DFS (Depth First Search)

- 깊이 우선 탐색

- 한 방향으로 끝까지 진행

- 더 이상 갈 곳이 없으면, 가장 가까운 곳으로 다시 되돌아가서(backtracking) 해당 지점에서부터 다시 탐색을 시작

 

▶ 구현 방법

1. 인접 행렬

2. 인접 리스트

• 순환 호출 사용
• stack 사용 : 인접 정점들을 stack에 저장했다가 꺼내서 다시 탐색

 

 

BFS (Breath First Search)

- 너비 우선 탐색

- 현재 정점으로부터 가장 가까운 노드를 먼저 방문

- 멀리 떨어져 있는 정점은 나중에 방문

 

▶ 구현 방법

1. 인접 행렬

2. 인접 리스트

• 인접 행렬/리스트 모두 큐를 이용해서 구현

 

 

DFS / BFS 활용 문제

- 검색 대상 그래프가 매우 큼 = DFS

- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다 =  BFS

 

1) 모든 정점을 방문(탐색)

• DFS, BFS 둘다 사용

 

2) 경로의 특징을 저장 (가중치 관리, 탐색 제약조건 존재)

• DFS 사용
• ex) 이동할 때마다 가중치 추가, 이동 시 여러 제약 존재,...etc

 

3) 최단거리 구하기 / 가중치 X

• BFS 사용
• ex) 미로찾기,...