너비우선탐색
-
[NetworkX] 너비 우선 탐색, 트리 구조 그리기Data & ML & AI/NetworkX 2022. 11. 2. 02:13
너비 우선 탐색 Breadth-First Search, BFS 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. (출처: 위키백과) 그래프의 한 노드에서 다른 모든 노드까지의 길이를 구하는 (그나마) 효율적인 방법 중 하나 아래는 A 노드가 다른 노드들과 얼마나 떨어져있는지 확인하기 위해 너비우선탐색을 진행한 결과입니다. A 본인의 주변 탐색 Distance1 : A와 연결되어있는 B, K의 주변 탐색 Di..