DFS / BFS 정리

출처, 자세한 내용 : youtu.be/7C9RgOcvkvo

 

DFS Depth First Search, 깊이 우선 탐색은 인접된 노드들을 깊이 우선으로 탐색하는 방법이다.

BFS Breadth First Search, 너비 우선 탐색은 인접된 노드들을 너비 우선으로 탐색하는 방법이다.

 

DFS는 스택을 사용해 구현한다. 파이썬은 일반 list를 선언해 사용하면 된다. -> 보통 재귀함수와 같이 사용한다.

 

1. 탐색 시작 노드를 스택에 넣고 방문 처리한다.

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.

-> 만약 방문하지 않은 인접 노드가 여러개라면 제시된 기준으로 선택한다.

-> 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복한다.

 

 

Bfs는 queue를 사용해 구현한다. (from collections import deque) -> 보통 큐를 구현한 뒤, 삽입,삭제를 반복해서 큐가 비어 있을 때까지 반복한다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.

3. 더 이상 2번의 과정을 수행할 없을 때까지 반복한다.