BFS1 [강의노트] 그래프 순회 -2 (BFS) 그래푸 순회 - 2(BFS) 지난 포스트에서는 DFS에 다루어보았고, 이번에 배울것은 BFS 너비우선탐색이다. 마찬가지로 그래프 순회 기법이다. BFS - 너비우선탐색 너비우선탐색에서 가장 핵심적인 단어를 꼽자면 level 이라고 생각한다. 이 얘기는 뒤에 몇번 더 언급하겠다. BFS는 트리의 level 별로 순회를 한다. 즉 트리에서 루트노드를 기준으로 자식노드로 계속 내려가는 것을 깊이우선탐색이라고 한다면, 기준노드에서 형제노드를 우선적으로 탐색하는 것이 너비우선탐색이다. DFS와는 탐색의 방향성 측면에서 어떻게 보면 반대의 개념이라고도 생각할 수 있다. BFS를 확장해서 해결 가능한 문제를 살펴보자. 두개의 주어진 정점 사이의 최소 간선을 사용하는 경로를 찾을 수 있다고 한다. 그래프 내 싸이클을 .. 2021. 11. 17. 이전 1 다음
