그래프 기반 탐색, DFS & BFS

DFS / BFS 란? 

그래프 탐색 알고리즘들 이다.

이들을 사용해서 구할 수 있는건 무엇인가?

1) 최단 경로 구하기 

2) 지나온 경로 구하기

3) 사이클링 구하기

4) 조합 수들 구하기

정도가 있다.

 

DFS / BFS 의 차이점은 무엇인가?

1) DFS 

=> 루트에서 시작해서 시작한 가지를 완전히 탐색 후 다음 분기를 탐색하는 방식

=> Stack, 재귀함수를 이용해 구현한다.

 

a) 장점 

i) 인접한 관계가 아닌 Depth 상 깊이 있을때, BFS 보다 더 우선적으로 탐색된다.

ii) 일련의 다른분기로 넘어가기 전에, 끝까지 탐색하면서 완전 탐색을 수행한다.

 

b) 단점

i) 앞 선, 가지의 수가 많은 경우에 매우 비효율적이다.

 

c) 사용효율

i)  모든 노드를 방문 할 경우, DFS

ii) 서로 다른 노드에서 두 노드 사이의 최단거리를 구할때, BFS

iii) 검색 속도에서는 BFS

iv) 탐색 그래프가 크고, 경로를 저장시, DFS

v) 탐색 그래프고 작고, 최단거리만을 구할때, BFS

 

2) BFS 

=> 루트에서 시작해서 인접한 노드를 우선적으로 탐색하는 순회 방식.

=> 큐를 이용해서 구현한다.

 

a) 장점

i)  두 노드의 최단 거리를 구할때 DFS 보다 빠르게 구할 수 있다.

ii) 적은 메모리를 사용한다.

 

b) 단점

i) 최단 경로 탐색이 불가능하다.

ii) 경로가 존재하지 않아도 끝날때까지 탐색

 

두 방식의 차이점을 확인하자.

BFS  vs DFS

구현 코드

-> 코드를 날려먹어서 (10.10 업로드예정)

BFS - 코드 [C++]

DFS - 코드 [C++]