[DA] BFS, DFS
BFS(Breadth-First Search), 너비우선탐색
- 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
- O(V + E)
- Queue를 이용하여 구현
- deQueue 정점의 인접한 정점를 enQueue(이미 방문한 곳 제외)
DFS(Depth-First Search), 깊이우선탐색
- 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘
- O(V + E)
- Stack을 이용하여 구현
- 방문 가능한 곳 push, 방문할 곳 없으면 pop
Leave a comment