![]()
그래픽 탐색이란? 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것 EX) 특정 도시에서 다른 도시로 갈 수 있는지 없는지 너비 우선 탐색 (BFS, Bredth-First-Search) 정의 루트 노드(혹은 임의의 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점부터 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문하는 방법 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다. 사용하는 곳 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때. 특징 1) 직관적이지 않은 점 - BFS는 시작 노드에서 거리에 따라 단계별로 탐색한다고 본다. 2) 재귀적인 동작을 하지 않는다. 3) 어떤 노드를 방문했는지 여부를 기록하여 무한루프에 빠질 위험을 제거 4) 방문..
![]()
깊이 우선 탐색 (DFS, Depth-First-Search) 정의 루트 노드 (혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 넓게 탐색하기 전에 깊게 탐색하는 것이다. 특징 1) 깊이 우선이 너비 우선(BFS)보다 간단하지만 느리다. 2) 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다. 3) 전위 순회(Pre-Order Traversals) 를 포함한 다른 형태의 순회는 모두 DFS의 한 종류이다. 주의점 그래프 탐색의 경우 어떤 노드를 방문했는지 검사해야 무한루프에 빠질 위험이 없다. 동작원리 a노드(시작노드) 방문 - 방문을 표시한다 a와 인접한 노드들을 차례로 순회 - 인접한 노드가 없다면 종료 a와 이웃된 노드b를 방문했다..
