mondegreen

최소 신장 트리의 개념 신장 트리 중에서 사용된 간선의 가중치의 합이 최소인 트리' 최소 신장 트리의 특징 1) 무방향 가중치 그래프 2) 그래프 가중치의 합이 최소 3) N개의 정점이 있는 그래프에 대해 반드시 N-1개의 간선을 사용해야 함 4) 사이클을 포함하면 안 된다 => 사이클 포함 = 불필요한 간선 존재 최소 신장 트리의 실 사용 비용이 최소가 되어야 하는 도로망, 통신망과 같은 다양한 분야 최소 신장 트리 구현 1) 크루스칼(Kruskal); 그리디 알고리즘의 한 종류 => 희소 그래프 인 경우 적합 간선을 하나씩 선택하며 MST를 찾는 알고리즘 (1) 모든 간선을 가중치에 따라 오름차순 정렬 (2) 가중치가 낮은 간선부터 선택하며 트리 증가 => 사이클이 존재*하면 그 다음 가중치를 가진 ..