그래프

그래프와 트리

그래프

단순히 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조

트리

방향성 있는 비순환 그래프의 한 종류

탐색

DFS

• 깊이 우선 탐색
• 다음 분기를 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 정점의 수 : N, 간선의 수 : E
  • 인접 리스트로 표현된 그래프 : O(N+E)
  • 인접 행렬로 표현된 그래프 : O(N^2)

BFS

• 너비 우선 탐색
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문
• 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• 정점의 수 : N, 간선의 수 : E
  • 인접 리스트로 표현된 그래프 : O(N+E)
  • 인접 행렬로 표현된 그래프 : O(N^2)