| 그래프 알고리즘 | 그래프에서 어떻게 쓰이는지 |
|---|---|
| 유니온 파인드(Union-Find) | 그래프의 사이클이 생성되는지 판별하는 알고리즘 |
| 위상 정렬(Topological sort) | 방향이 있고 사이클이 없는 노드와 에지를 갖는 그래프를 정렬하는 알고리즘 |
| 정렬 결과가 꼭 1개는 아님 | |
| ex) 수강신청, 게임 빌드 오더 | |
| 다익스트라(Dijkstra) | 시작점이 있고 다른 모든 노드로의 최단거리를 구하는 알고리즘 |
| (음수간선은 있으면 안됨) | |
| 벨만-포드(Bellman-Ford) | 시작점이 있고 다른 모든 노드로의 최단거리를 구하는 알고리즘 |
| (음수간선도 가능) | |
| 음수 사이클이 있는지 체크하는 문제가 더 많이 나옴 | |
| 플로이드-워셜(Floyd-Warchall) | 시작점이 없고, 임의의 모든 노드 쌍의 최단거리를 구하는 알고리즘 |
| (시간 복잡도가 안좋음) | |
| 최소 신장 트리(MST, Minimum Spanning Tree) | 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘 |
| (사이클이 나올 수 없게끔 유니온 파인드를 이용함) |