그래프의 탐색 방법 중에는 크게 깊이우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다.
이 탐색 방법들의 목적은 모든 정점을 1번씩 방문하는 것이다.
DFS는 최대한 깊숙히 탐색.
BFS는 최대한 넓게 탐색한다.
DFS는 스택을 이용하고 BFS는 큐를 이용한다.
BFS는 모든 간선의 가중치가 1일 때 최단거리를 탐색하는 알고리즘이 된다.
*DFS
check[i] =1 or 0 을 사용해 방문 여부를 저장한다.
시간복잡도는 인접행렬을 사용했을 때는 O(V^2), 인접리스트를 사용하면 O(V+E)이다.
*BFS
시간복잡도 인접행렬 : O(V^2) 리스트: O(V+E)
'컴퓨터 공학 > 자료구조, 알고리즘' 카테고리의 다른 글
| 그래프 기초 (0) | 2021.01.02 |
|---|---|
| bfs와 dfs 구현해보기 (0) | 2019.07.18 |
| C++ 간단한 버블 소트 (Bubble Sort) 배우기 (0) | 2019.06.24 |