크루스칼알고리즘 썸네일형 리스트형 [알고리즘] MST 최소 신장 (스패닝) 트리 /* 최소 신장 트리(MST) */최소 신장 트리(Minimum Spanning Tree, MST)는 가중치 그래프에서 모든 정점을 연결하는 최소 비용의 부분 그래프입니다. MST는 사이클이 없고, (V - 1)개의 간선을 가지며, 그래프의 최소 연결 비용을 찾는 데 사용됩니다.MST의 특징연결 그래프: 모든 정점이 연결되어 있어야 합니다.최소 비용: 간선의 가중치 합이 최소가 되어야 합니다.사이클이 없어야 함: 트리의 성질을 만족해야 합니다.(V - 1)개의 간선: 정점이 V개라면, MST의 간선 수는 항상 (V - 1)개입니다./* 첫 번째 알고리즘, 크루스칼 알고리즘*/크루스칼 알고리즘은 간선을 가중치 기준으로 정렬한 후, 최소 비용의 간선을 하나씩 선택하여 MST를 구성하는 방식입니다.시간 복잡도.. 더보기 이전 1 다음
