내가보려고만든 메자노트

최소 스패닝 트리(Minimum Spannig Tree) = 최소 신장 트리 : 스패닝 트리 중 가장 작은 가중치의 간선으로 구성된 트리를 의미한다. 조건 본래의 그래프의 모든 노드를 포함 간선의 가중치의 합이 최소여야 한다 모든 노드가 서로 연결되어있다 트리의 속성을 만족 (사이클이 존재하지 않는다) ↓스패닝 트리란? 더보기 스패닝 트리란? : 그래프의 최소 개수의 간선으로 이뤄진 트리 (n개의 노드가 존재한다면 간선은 항상 n-1개이다) 모든 노드가 연결되어야 함 사이클이 존재하지 않음 즉, 최소 스패닝 트리에서 최소 가중치의 합 조건만 빠진 트리를 의미. 이 최소 스패닝 트리 문제를 다루는 알고리즘에는 2가지가 있다. 1. 크루스 칼(Kruskal) 알고리즘 : 두 노드 간 제일 작은 가중치의 간선..