210708 너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS)

너비 우선 탐색(BFS, Breadth - First Search)

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

즉 깊게 보다 넓게를 우선시한 탐색

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 활용함

 

BFS의 과정

1. 시작 정점 방문 
2. 깊이 1인 모든 노드 방문
3. 깊이 2인 모든 노드 방문.... (반복)
4. 더 이상 방문할 곳 없으면 탐색 마침 

노드 방문 세부 과정은

1. (큐에서 꺼낸) 노드를 방문하였을 경우
2.  큐에서 꺼낸 노드 방문 
3.  큐에서 꺼낸 노드와 인접한 노드들 모두 방문
4.  방문한 노드들 큐에 삽입, 더 이상 없다면 큐에서 노드 꺼냄 

이런 과정을 반복한다 

 

 

예시

 

시간복잡도 : 

• 인접 행렬 사용시 : O(노드수 +간선수)
• 인접 리스트 사용시 : O(노드수^2)

 

깊이 우선 탐색(DFS, Depth - First Search)

 

BFS 가 깊이가 1인 곳을 탐색하고 깊이가 2인 곳을 탐색했다면

DFS 는 루트 노드에서 시작하여 더 이상 탐색할 수 없을 때까지 탐색하고 더 이상 진행할 수 없으면 가까운 갈림길로 돌아와서 다시 탐색하는 방식 

즉 넓게 보다 깊게 탐색하는 방식

모든 노드를 방문하고자 하는 경우에 사용

 

 

예시

시간복잡도 : 

• 인접 행렬 사용시 : O(노드수 +간선수)
• 인접 리스트 사용시 : O(노드수^2)