[알고리즘] 최소신장트리와 크루스칼 알고리즘의 이해

1. 신장 트리 란?

• Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임)
• 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프
• 신장 트리의 조건
  • 본래의 그래프의 모든 노드를 포함해야 함
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족시킴 (사이클이 존재하지 않음)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기