목차

• 그래프 탐색이란
• 깊이 우선 탐색

# 그래프 탐색이란

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
• Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 등등

# 그래프 탐색

그래프를 탐색하는 방법에는 널리 사용되는 두 가지 방식이 있다.

• DFS는 깊이 우선 탐색(Depth-First Search)이다.
• BFS는 너비 우선 탐색(Breadth-First Search)이다.
• 먼저 그래프라는 자료구조에 대한 지식이 있어야 한다.