TDL
BFS, DFS
NOTE3
-
BFS(breadth-first Search)
- 넓이우선탐색
- 큐의 개념이 사용(FIFO,선입선출)
- 활용:
- 길찾기, 라우팅- BitTorrent와 같은 P2P 네트워크에서 인접 노드 찾기
- 웹 크롤러
- 소셜 네트워크에서 멀리 떨어진 사람 찾기
- 그래프에서 주변 위치 찾기
- 네트워크에서 방송
- 그래프에서 주기 감지
- 연결된 구성 요소 찾기
- 몇 가지 이론적 그래프 문제 풀기
- BFS는 큐 자료구조를 활용하고 재귀호출은 하지 않는다.
- BFS는 노드가 적은 경우 최단경로를 탐색할 때 유용함.- 큐를 활용하므로 노드가 많아지면 메모리 저장공간이 증가하는 단점이 있음.
- 재귀적으로 동작하지 않는 이유는 인접한 노드에 대해 먼저 탐색을 하기 때문에 재귀적으로 재호출할 필요가 없음.
- BFS 장점:
- 최단경로를 찾기 적합- 찾는 노드가 인접한 경우 효과적
- BFS 단점:
- Queue를 이용해 노드를 저장하기 때문에 노드의 수가 많을수록 메모리 소비가 큼.
-
DFS(Depth-first Search)
- 깊이우선탐색
- 스택(Stack)의 개념(LIFO,후입선출)
- 다른 경로를 역추적하고 탐색하기 전에 가능한 그래프를 분할함.
- 분할의 의미는 깊이별로 탐색하기 때문에, 내부적으로 그래프가 선 분할된 후 탐색을 진행
- 즉, 탐색->분할->탐색
- backtracking(역추적)
- DFS에서 활용되는 방법. 노드가 있을만한 곳을 되돌아가서 모두 살펴본다는 개념- DFS는 깊이 우선적으로 탐색하고, 재귀적으로 아래에서부터 탐색하지 않은 정점이 있는지 확인하는 방법이다.
- DFS 활용:
- 가중 그래프의 최소 스패닝 트리 찾기- 길 찾기
- 그래프에서 주기 감지
- 미로 문제
- DFS 장점:
- 찾는 노드의 depth가 깊을수록 빠르다.- 메모리 적게 차지
- DFS 단점:
- 노드가 무한한 갯수로 존재하는 경우, 무한반복(루프)에 빠진다.
-
BFT, DFT (Traversal) 순회라고도 함.
- 순회는 트리와 그래프 같은 연결구조에서 노드를 방문하는데 사용되는데, BFS,DFS는 순회(방문)하면서 탐색하는 탐색알고리즘이다.
- 출발지 노드와 그래프/트리 구조에 따라 탐색하는 순서와 노드가 달라질 수 있다.
-
deque : double-ended queue
- 양방향 처리(큐의 양쪽 끝에서 삽입과 삭제 모두 가능)
- from colections import deque
- append(), appendleft()
- pop(), popleft()
- extend(), extendleft(), rotate(), reverse()
https://gggggeun.tistory.com/