[알고리즘] 그래프 - 깊이 우선 탐색(dfs), 너비 우선 탐색(bfs) / 전체 탐색 - 브루트 포스 기법 정리

그래프는 노드와 링크로 구성되어 있다.

깊이 우선 탐색(dfs, depth-first search)

- 깊은 부분을 우선적으로 탐색하는 알고리즘

- 탐색 할때 특정한 경로를타고 밑바닥까지 내려간 후 막다른 길에 도착하면 다시 돌아와 다른 경로를 탐색

- 스택 자료구조 (FILO)

 

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택

2. 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단함

3. 검색 속도 자체는 너비 우선 탐색에 비해서 느림

 

 

너비 우선 탐색 (bfs, breadth-first search)

- 최대한 넓게 이동한 다음 ,더 이상 갈 수 없을 때 아래로 이

- 가까운 노드부터 탐색하는 알고리즘 

- 큐 자료구조를 이용하여 표현 된다

 

 

 

브루트 포스 

브루트 포스는 완전 탐색 알고리즘 - 가능한 모든 경우의 수를 탐색하는

알고리즘을 설계할 때 해가 하나 이상 존재한다는 가정을 세우고 모든 범위르 탐색하기 때문에 무조건 정답 찾기 가능

장점	단점
- 알고리즘을 설계하고 구현하기 매우 쉽다 - 복잡한 알고리즘 없이 빠르게 구현할 수 있다.	- 알고리즘의 실행 기간이 매우 오래 걸림 - 메모리 효뮬면에서 매우 비효율적
종류
- 선형 구조 : 순차 탐색 - 비선형 구조 : 백트래킹,   DFS, BFS