그래프 탐색알고리즘

• 그래프 : 여러 개체들이 연결되어 있는 자료 구조

• 탐색 : 특정 개체를 찾기 위한 알고리즘

• 대표적 문제 유형

  • 경로탐색 유형 (최단거리, 시간) : A지점부터 B지점까지의 최단거리 구하기나 최소거리 구하는 문제
  • 네트워크 유형 (연결) : 연결되어 있는 그룹의 개수를 구하거나, 두 개체가 같은 네트워크 안에 있는지 구하는 문제
  • 조합 유형 (모든 조합 만들기) : 여러 가지의 조합을 전부 만들거나 비교하는 문제

• 예시

BFS와 DFS

구현 방법

• DFS : 재귀함수나 스택. 재귀함수로 구현하는 것이 일반적
• BFS : Queue나 LinkedList