시카로의 공부방

최소 신장 트리 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘. 그 중에서 대표적인 최소 신장 트리 알고리즘이 크루스칼 알고리즘 그리디 알고리즘으로 분류 신장 트리의 개념 하나의 그래프가 있을 때 모든 노드를 포함하고, 연결되며 사이클이 존재하지 않는(tree) 그래프 신장 트리는 구글에 치기만 해도 예시가 나온다. 연결 관계에서 사이클을 형성하지 않으므로, 정점의 개수가 n개일 때, 간선이 n-1개가 된다. 최소 신장 트리 해당 신장 트리들 중에서 간선에 부여된 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라 한다. 신장 트리의 조건을 만족하면서 최소 가중치(비용)을 들이는 신장 트리가 최소 신장 트리이다. 크루스칼 알고리즘 크루스칼 알고리즘의 구체적인 동작..