그래프를 순회하는 방법으로 DFS(Depth First Search)와 BFS(Breadth
First Search)가 있다.
DFS
깊이 우선 탐색
- n개의 정점과 m개의 간선을 가지는 그래프의 DFS는 O(n+m)의 실행시간을 필요로 한다.
- 재귀를 통해서 구현할 수 있다.
- 위의 그래프에서는 A, B, C, E, D의 순서로 방문한다.
- 선위 순회와 유사하다.
- 두 정점 사이의 경로와 싸이클을 찾을 수 있다.
BFS
너비 우선 탐색
- n개의 정점과 m개의 간선을 가지는 그래프의 BFS는 O(n+m)의 실행시간을 필요로 한다.
- 큐를 통해서 구현할 수 있다.
- 위의 그래프에서는 A, B, D, C, E의 순서로 방문한다.
- 레벨 순회와 유사하다.
BFS를 통해서 최소 간선을 이용하는 두 정점의 경로, 그래프 내의 단순 싸이클을 찾을 수 있다.
🙌🙌🙌🙌