[알고리즘] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

[알고리즘] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

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

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

• 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
• 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 위의 과정을 더이상 수행할 수 없을 때까지 반복한다. 

 

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

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중, 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
• 위의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

 

참고

https://devuna.tistory.com/32