[자료구조] 깊이우선탐색(DFS) vs 너비우선탐색(BFS)

 

https://velog.io/@vagabondms/DFS-vs-BFS

===개념 요약===

	DFS(Depth-First Search)	BFS(Breadth-First Search)
기본개념	시작노드에서 부터 탐색할 수 있는 최대 깊이로 탐색을 진행한 후, 되돌아 가며 방문하지 않은 노드를 방문한다.	시작노드에서부터 인접한 노드 부터 모두 방문하며,  방문한 노드를 큐에 저장하고 먼저 저장된 노드부터 출력한다.
구현방법	스택, 재귀	큐
사용목적	미로찾기, 그래프 구조파악	최단거리(가중치x), 노드간 최단거리

 

===기본 자료구조===

	스택(stack)	큐(queue)
기본 개념	쌓아간다는 의미로, 한쪽(rear)에서만 시간순서에 따라 데이터가 쌓이고 역순으로 데이터가 빠져나가는 구조를 가진다.	줄을 선다는 의미로, 한쪽(rear, 뒤)에서는 데이터가 들어오고 반대쪽에(front, 앞)서는 나가는 구조를 가진다.
구조 요약	LIPO(or PILO, Last In First Out): 후입선출	FIFO(or LILO, First In First Out): 선입선출
사용 목적	데이터를 쌓아 역순으로 처리할 때 사용 / DFS 구현	들어온 순서대로 처리해야할때 / BFS 구현
비고	- 빈 스택에서 데이터 추출: stack underflow - 스택이 넘치는 것 : stack overflow - stack = list()	- deque: 양방향에서 push/pop이 모두 가능한 구조 - from collections import deque - q = deque(list)