[알고리즘] BFS DFS

그래프 탐색: 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법

BFS: Breadth-first search(너비 우선 탐색)

DFS: Depth-first search(깊이 우선 탐색)

 

# BFS

## 아이디어

시작점에 연결된 Vertex 찾기

찾은 Vertex를 Queue에 저장

Queue의 가장 먼저 것 뽑아서 반복

 

## 시간복잡도

O(V+E)

(1초 연산 2억개)

 

## 자료구조

검색할 그래프

방문여부 확인

BFS 실행할 Queue

 

# DFS
## 아이디어

시작점에 연결된 Vertex 찾기

연결된 Vertex를 계속해서 찾음(끝날때까지)

더이상 연결된 Vertex 없을 경우 다음

 

## 시간복잡도

O(V+E)

 

## 자료구조

검색할 그래프

방문여부 확인