BFS와 DFS는 그래프 탐색 알고리즘이다.

그래프 탐색이란,

하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것 (시작점은 우리가 정할수있음)
그래프를 효율적으로 사용하기 위해서는 꼭! 알아야한다.

BFS (Breadth First Search)

너비 우선 탐색

큐를 이용한 구현 (First In First Out)

맨 뒤 데이터 삽입
맨 앞 데이터 삭제 및 접근

BFS 알고리즘 간략한 순서

1. 우선 처음 시작할 때 시작 노드를 큐에 넣어준다.
2. 해당 큐안에 아무것도 없을 때까지 아래 작업을 반복한다.
3. 큐 가장 앞 노드를 꺼낸 후 해당 노드의 인접 노드들을 탐색한다.
4. 탐색한 노드가 처음 방문한 노드일 시 큐에 넣어준다.
5. 3부터 4번 작업을 반복해준다.

시간복잡도

총 노드의 수 : V
엣지의 수 : E

1. 노드 전처리

• 방문하지 않는 노드를 노드의 개수만큼 확인을 해야하기 때문에 O(V)의 시간복잡도가 걸린다.

2. 큐의 노드를 넣고 빼는데 걸리는 시간

• 각 노드는 큐에 한번씩만 들어갔다 나오는데, 큐가 더블 링크드 리스트로 구현되어있을 때 삽입, 추출은 O(1)의 시간복잡도를 가지고 있다. 그러므로 노드의 개수만큼 넣다 뺏다를 반복할 때 O(V)가 걸린다고 할 수 있다.

3. 큐에서 뺀 노드의 인접한 노드들을 도는데 걸리는 시간

• 큐에서 나온 노드는 인접한 노드들을 각 한번씩 돌기 때문에 O(E)(총 엣지의 개수만큼)가 걸린다고 할 수 있다.

∴ 결과

• 위의 세개를 더하면 총 O(2V + E)의 시간복잡도가 나오는데 통상 상수는 무시하기 때문에 O(V+E) 의 시간 복잡도가 걸린다고 할 수 있다.

DFS (Depth First Search)

깊이 우선 탐색

스택을 이용한 구현 (Last In First Out)

맨 뒤에 데이터 추가
맨 뒤 데이터 삭제
맨 뒤 데이터 접근

DFS 알고리즘 (간략한 순서)

1. 처음 시작 시 시작 노드를 스택에 넣어준다.
2. 해당 스택안에 노드가 없어 질때까지 아래 순서를 반복한다.
3. 스택 맨 위 노드를 먼저 방문한다.
4. 방문한 노드는 스택에서 제거해주고 해당 노드의 인접 노드들을 탐색한다.
5. 인접 노드들 중 방문하지 않은 노드면 스택에 넣어주고 아니면 skip 한다.
6. 위 3부터 5번 작업을 반복해준다.

시간 복잡도

1. DFS 노드 전처리

• 방문하지 않는 노드를 노드의 개수만큼 확인을 해야하기 때문에 O(V)의 시간복잡도가 걸린다.

2. 스택에 노드를 넣고 빼는데 걸리는 시간

• 각 노드는 스택에 한번씩만 들어갔다 나오는데, 스택이 더블 링크드 리스트로 구현되어있을 때 삽입, 추출은 O(1)의 시간복잡도를 가진다. 그러므로 노드의 개수만큼 넣다 뺏다를 반복할 때는 O(V)가 걸린다고 할 수 있다.

3. 스택에서 뺀 노드들의 인접한 노드들을 도는데 걸리는 시간

• 스택에서 나온 노드는 인접한 노드들을 각 한번씩 돌기 때문에 O(E)(총 엣지의 개수만큼)가 걸린다고 할 수 있다.

∴ 결과

• 위의 세개를 더하면 총 O(2V + E)의 시간복잡도가 나오는데 통상 상수는 무시하기 때문에 O(V+E) 의 시간 복잡도가 걸린다고 할 수 있다.