BFS
-
DFS & BFS알고리즘 2020. 3. 16. 16:50
들어가기 전, 그래프의 탐색이란? 어떤 정점에서 출발하여 그래프의 모든 정점을 방문하는 것 깊이를 우선으로 하는 깊이 우선 탐색과 너비를 우선으로 하는 너비 우선 탐색이 있다. 1. DFS (Depth First Search) 깊이 우선 탐색 개념? 현재 정점에서 이동할 수 있는 점들까지 들어가면서 탐색하는 방법 모든 정점(혹은 노드라고도 부름)를 방문하고자 하는 경우에 사용 다른 정점으로 이동할 수 없을때, 이전 정점으로 돌아가야하므로 거쳐온 정점들을 모두 저장해 주어야 한다. 구현 방법? 스택 또는 재귀함수로 구현, 즉 후입선출(LIFO) 원칙으로 탐색 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다. *검사안할 경우 무한루프에 빠질 수 있다.* (ex) 2. BFS (Breadth Frist S..