본문 바로가기

그래프의 탐색

[자료구조] 그래프(Graph)의 탐색 및 구현
[자료구조] 그래프(Graph)의 탐색 및 구현 2024. 3. 29. 📌 그래프(Graph)의 탐색 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적입니다. 원하는 값만 한 번에 찾고 싶지만 그래프의 데이터는 배열처럼 정렬이 되어 있지 않기 때문에, 원하는 자료를 찾으려면 하나씩 모두 방문하여 찾아야 합니다. 그래프의 탐색에는 크게 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)이 있습니다. 1. 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것..

티스토리툴바