[Algorithm] BFS, DFS

[Algorithm] BFS, DFS

그래프 탐색 알고리즘의 두가지 BFS, DFS이다.

그래프 : 정점(node)과 정점들을 이어주는 간선(edge)으로 이루어진 자료구조

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

그래프에서 인접한 노드부터 우선적으로 탐색하는 알고리즘

시작 정점으로부터 인접한 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 방법

- Queue를 이용하여 구현

BFS 탐색 순서

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

그래프에서 깊게 내려간 다음, 더 이상 깊게 갈 곳에 없을 때 옆으로 이동

임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- STACK or 재귀함수를 이용하여 구현

DFS 탐색 순서

※ 문제 유형별 유리한 탐색 방법

모든 정점을 방문 DFS, BFS 최단 거리 BFS 경로의 특징 DFS

from http://young-library.tistory.com/93 by ccl(A) rewrite - 2021-08-01 21:26:21