목록BFS (1)

처음부터 차근차근

[알고리즘] BFS

너비 우선 탐색(BFS)이란?? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 의미한다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다., 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. DFS의 경우 BFS보다 좀 더 복잡하다. BFS의 특징 시작 노드에서 시작해서 거리에 따라 단계별로 탐색하기 때문에 직관적이지 않은 면이 있다. 재귀적으로 동작하지 않는다. 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 그렇지 않으면 무한 루프에 빠질 위험이 있다. BFS는 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 즉, ..
CS/알고리즘 2023. 11. 16. 11:14
이전 Prev 1 Next 다음