먼저 그래프를 소스코드로 표현하자
그래프를 탐색하는 두 가지 방법이 있다.
너비우선탐색과 깊이우선탐색이다...
너비 우선 탐색 Breadth First Search(BFS)
정점과 같은 레벨에 있는 노드들을 탐색하는 방식이다.
이것을 소스코드로 표현하면
시간 복잡도는?
노드수(V) + 간선수(E)
O(V+E)
깊이 우선 탐색 Depth First Search(DFS)
정점의 자식들을 먼저 탐색하는 방식이다.
이것을 소스코드로 표현하면
차이점은 스택을 쓴 것밖에 없다...
'컴퓨터공학 > 자료구조&알고리즘' 카테고리의 다른 글
| 코딩테스트> 고급 정렬 알고리즘 연습문제 (0) | 2021.05.05 |
|---|---|
| 코딩테스트> 기본 자료 구조와 정렬 연습문제 (0) | 2021.04.16 |
| 알고리즘> 고급> 분할정복법> 퀵정렬 (0) | 2021.03.12 |
| 알고리즘> 탐욕 알고리즘 (0) | 2021.03.12 |
| 알고리즘> 그래프> 다익스트라 알고리즘 탐색 기법 (0) | 2021.03.12 |
