그래프 알고리즘

---

✅ 유니온 파인드

그래프에서 사이클이 생성되는지 판별하는 알고리즘

---

✅ 위상정렬

조건 ) 
1. 사이클이 없고
2.방향이 있는(전후 관계가 있는) 그래프일 때

그래프를 정렬해주는 알고리즘

정렬결과가 꼭 하나는 아니다.

예) 수강신청(A를 듣고 B를 들어야 한다 등)

---

✅ 다익스트라, 벨만-포드, 플로이드-워셜

세 개 노드 사이의 최단 거리를 구하는 알고리즘이다.

• 다익스트라

시작점이 있고, 다른 모든 노드로 가능 최단 거리를 구하는 알고리즘
단, 음수 간선은 안된다!

• 벨만-포드

시작점이 있고, 다른 모든 노드로 가능 최단 거리를 구하는 알고리즘
음수 간선 가능!
음수 싸이클이 존재하는지에 대한 문제로 많이 출제된다.

예) 시간 여행을 할 수 있는지 여부 (= 음수 간선이 존재하는지)

• 플로이드-워셜

시작점이 없고, 모든 노드에 대해 가능 최단 거리를 구하는 알고리즘
위에 2가지에 비해 시간 복잡도가 크다.
즉, 입력값이 작을 때, 시작점이 없을 때 사용한다.

---

✅ 최소 신장 트리

모든 간선을 연결하는 최소의 비용을 구할 수 있게 해주는 알고리즘 
싸이클이 나올 수 없다.

유니온 파인드로 싸이클이 나오는 것을 방지해주는 코드가 등장한다.

---

저번부터 이미지 업로드 왜 자꾸 실패함?