들어가기 전에

그래프 개념을 알아야 함

그래프 탐색 알고리즘

• BFS / DFS
• 그래프를 대상으로 하는 탐색 알고리즘
• 그래프를 탐색한다는 것은, 하나의 노드로부터 시작하여 차례대로 모든 노드들을 한 번씩 방문하는 것

BFS

• Breadth-First Search, 너비 우선 탐색

• 루트 노드(or 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법
  • 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문

<aside> 💡 아래와 같은 질문에 대답하는 데 도움을 줌

1. 정점 A에서 정점 B로 가는 경로가 존재하는가? → 최단 경로 찾기
2. 정점 A에서 정점 B로 가는 최단 경로는 무엇인가? </aside>

구현

• 큐로 구현

시간복잡도

인접 행렬 → $O(v^2)$

인접 리스트 → $O(v+e)$

DFS

• Depth-First Search, 깊이 우선 탐색