반응형
그래프 탐색
-
그래프의 탐색 - BFS, DFSAlgorithm/이론 2023. 1. 11. 17:03
1. 너비 우선 탐색(BFS) 1) 개념 너비 우선 탐색(BFS, Breadth-First Search)란 루트 노드 부터 시작해 인접한 노드를 우선적으로 탐색하는 방법이다. 이름 그대로 넓게 탐색하는 방법이며, 두 노드 사이의 최단 경로를 구하는 문제를 해결하는데 효과적이다. BFS의 구현과 이해는 Queue와 그래프에 대한 이해를 바탕으로 한다. 이에 대한 내용은 아래 글을 참고하면 된다. [ 선형 자료구조 ] 스택(Stack) & 큐(Queue) 1. Stack 1) 개념 스택은 LIFO(last-in-first-out), 즉, 후입선출 원칙을 따르는 선형 자료구조이다. 따라서 데이터의 출입은 한 방향에서만 이루어지고, 이름에 걸맞게 쌓아가는 구조를 가진다. 데이터에 ojhallae.tistory...