Algorithm/Study
2021. 9. 17.
그래프 탐색 알고리즘 : BFS (Python)
BFS - 개념 : 가까운 노드부터 탐색하는 너비 우선 탐색 알고리즘 (DFS는 최대한 멀리 있는 노드 우선 탐색) - 큐 자료구조 이용 (= 파이썬 deque 라이브러리) - 시간 복잡도 : O(N). (실제 수행 시간은 DFS보다 좋은 편이다. 이유 - DFS의 재귀함수 사용) - 장점 : 1) 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단경로임을 보장한다. 2) 노드의 수가 적고 깊이가 얕은 해가 존재할 때 효과적이다. - 단점 : 1) 큐를 이용해서 다음에 탐색할 노드를 저장하기 때문에 더 큰 저장공간이 필요하다. 2) 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기 때문에 비효율적이다. - 사용예 : 최단경로, 최소신장트리 - 구현 방식 : 인접한 ..
