크루스칼 알고리즘1 신장 트리 신장 트리란? Spanning Tree, 또는 신장 트리라 불린다. 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 말한다. 조건은 다음과 같다 - 본래의 그래프의 모든 노드를 포함해야한다. - 모든 노드가 서로 연결되어야 한다. - 트리의 속성을 만족시켜야 한다. (사이클이 존재하지 않는다.) 최소 신장 트리 MST 가능한 ST 중에서 간선의 가중치 합의 최소인 ST를 지칭한다. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재한다. 대표적으로 크루스 칼 알고리즘과 프림 알고리즘이 있다. 1) 크루스칼 알고리즘 1. 모든 정점을 독립적인 집합으로 만든다. 2. 모든 간선을 비용 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 .. 2020. 9. 9. 이전 1 다음
