🌐 그래프 알고리즘 정리

---

🔗 1. 유니온 파인드 (Union-Find)

그래프에서 사이클 발생 여부를 판별하는 알고리즘.
노드들을 그룹(집합)으로 관리하면서, 두 노드를 연결할 때 사이클이 생기는지 확인할 수 있다.

✅ 활용: 최소 신장 트리(MST, Kruskal) 구현 시 필요

---

🔀 2. 위상 정렬 (Topological Sort)

• 조건: 사이클이 없는 방향 그래프(DAG)여야 함
• 노드와 간선을 순서 있게 나열하는 알고리즘
• 결과는 여러 가지 형태가 나올 수 있음

📌 예시

• 📚 수강신청 과목 순서 (수학1 → 수학2)
• 🎮 스타크래프트 테크트리

---

🛣️ 3. 최단 거리 알고리즘

🚀 다익스트라 (Dijkstra)

• 시작점 S에서 다른 모든 노드까지 최단 거리 계산
• 단, 음수 간선 불가

---

⚡ 벨만-포드 (Bellman-Ford)

• 음수 간선 허용 가능
• 음수 사이클 판별까지 가능
• 음수 사이클 → 최단 거리 = -∞ (시간여행 개념으로 비유 가능 🚀🕰️)

---

🌍 플로이드-워셜 (Floyd-Warshall)

• 모든 노드 쌍 간 최단 거리 계산
• 시작점이 따로 없음
• 시간 복잡도 ↑ → (N < 500) 일 때 적합
• 예: 모든 도시 간 이동 시간 계산

---

🌲 4. 최소 신장 트리 (MST, Minimum Spanning Tree)

그래프에서 모든 노드를 최소 비용으로 연결하는 방법.

• 조건: 사이클이 없어야 함
• 결과: 모든 노드를 연결하면서 간선 가중치 합 최소
• 알고리즘: Kruskal, Prim 알고리즘
• 구현 시 유니온 파인드 활용

---

📌 전체 요약

• 🔄 사이클 판별 → 유니온 파인드
• 📐 순서 정하기 → 위상 정렬
• 🛤️ 최단 거리 → 다익스트라 / 벨만-포드 / 플로이드-워셜
• 🌲 모든 노드 연결 최소 비용 → MST