📌 그래프
- 노드와 에지로 구성된 집합
- 노드는 데이터를 표현하는 단위
- 에지는 노드를 연결
⭐ 유니온 파인드
- 그래프의 사이클이 생성되는지 판별하는 알고리즘
⭐ 위상 정렬
- 조건 : 싸이클x, 방향있는 그래프
ex) 수강신청(수1 -> 수2), 롤(bf대검 -> 무한의대검)
⭐ 다익스트라
- 최단거리 알고리즘
- start 시작점이 있고, 다른 모든 노드로 가는 최단거리를 구하는 알고리즘
- 제약사항 : 음수간선 X
⭐ 벨만-포드
- 최단거리 알고리즘
- start 시작점이 있고, 다른 모든 노드로 가는 최단거리를 구하는 알고리즘
- 음수간선 O
ex) 음수싸이클 여부
⭐ 플로이드-워셜
- 최단거리 알고리즘
- 시작점이 없음, 임의의 모든 노드쌍의 최단거리를 구하는 알고리즘
- 시간복잡도 안좋음
⭐ 최소신장트리(MST)
- 모든 노드를연결하는데 최소의 비용
- 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘
- 사이클 X(유니온파인드로 확인)
