그래프 문제를 풀때 도움이 되는 정보. (자세한 알고리즘은 기억하기...)
⭐ 그래프 표현
- 엣지 리스트 : 시작 노드, 끝 노드, 가중치를 가진 엣지 클래스를 만들어 이를 리스트로 사용.
- 인접 행렬: n * n의 2차원 배열을 만들어서 사용.
- 인접 리스트: 인접 행렬의 단점을 수정하기 위해서, 시작 노드별 끝 노드를 저장.
⭐ 유니온-파인드(Union-Find)
- 그래프 내의 사이클 유무를 확인하기 위해 사용한다. (노드별 대표노드를 찾아서, Union한다. 중요한 것은 Union과 Find시 대표노드를 간략화하여 시간복잡도를 줄이는 것.)
⭐ 위상 정렬
- 그래프 내에서 확실한 순서가 있고 이를 정렬하여 출력할때 사용한다. 사이클이 없는 방향이 있는 그래프에서 사용한다.
(값이 유일하지 않다.) - 인접 리스트와 배열, 큐를 이용한다.
ex) 줄세우기, 아이템 하위템, 수강신청
⭐ 다익스트라 알고리즘
- 양의 가중치만 있는 그래프의 경우 한 시작점에서 다른 모든 노드의 최단거리를 구하는 알고리즘. O(E log V)
- 인접리스트와 배열을 이용한다.
⭐ 벨만-포드 알고리즘
- 음의 가중치가 있는 경우에도 한 시작점에서 다른 모든 노드의 최단거리를 구할 수 있다. O(EV)
- 보통 음수 가중치가 있는 사이클을 찾을 때 주로 쓴다.
- 엣지리스트와 배열을 이용한다.
- 노드 갯수 - 1 만큼 반복했을 시, 최단거리 배열 완성. (한번 더 반복했을 시 변경되면 음수사이클 존재)
ex) 시간여행, 과거로 돌아간다, 웜홀, 워프
⭐ 플루이드-워셜 알고리즘
- 모든 점에서 모든 점까지의 최단거리를 구할 수 있다. 시간복잡도가 안좋다.
- 인접 행렬을 이용한다.
- 구현시 3중 for문을 사용한다.
for 경유지 K에 관해 (1 ~ N) { // N: 노드 개수 for 출발 노드 S에 관해 (1 ~ N) { for 도착 노드 E에 관해 (1 ~ N){ D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]); } } }
⭐ 최소 신장 트리 (MST) - 크루스칼 알고리즘
- 모든 노드를 연결할 때, 가중치가 최소가 되는 간선을 구하는 알고리즘. (유니온-파인드가 선행으로 필요하다. - 사이클이 없어야 하기 때문에)
- 엣지리스트를 이용한다.
