정리

그래프

• 그래프는 node와 edge로 이루어져 있다.

• 방향성과 순환성이 각각 있거나 없거나

  	--둘 다 없으면 트리 Tree

• 수많은 그래프 / 트리 종류와 알고리즘들이 존재한다.

그래프를 코드로 구현하는 2가지 방법

1. 인접행렬

• edge 가 많은 그래프일 때 쓰는데 좋다
• edge 탐색이 빠르다.

2. 인접리스트

• edge 가 적은 그래프일 때 쓰는게 좋다.
• 메모리 적게 쓴다.

완전탐색

DFS, BFS, 백트래킹은 전부 완전탐색 알고리즘

최악의 경우 모든 노드를 탐색하는 건 동일

• 최단 거리를 구 할 때는 BFS사용

• DFS는 재귀 (or 스택), BFS는 큐로 구현

• 가기치기를 하면 백트래킹