크루스칼 알고리즘 * 크루스칼 알고리즘 - 포리스트에서 어떤 두개의 트리를 연결하는 모든 간선중 가장 가중치가 작은 간선(u,v)를 찾는 것으로 포리스트에 추가할 안전 간선을 찾음. - 각 단계에서 가장 가중치가 작은 간선을 포리스트에 추가하기 때문에 그리디 알고리즘임 * 과정 1. 그래프의 각 정점이 각각 하나의 트리가 되도록 하는 포레스트 F을 만든다 2. 모든 변을 원소로 갖는 집합 S를 만든다 3. S가 비어있지 않는 동안 가장 작은 가중치의 변을 S에서 하나 빼낸다 4. 그 변이 어떠 두개의 트리를 연결한다면 두 트리를 연결하여 하나의 트리로 만든다 그렇지 않다면 그 변은 버린다 더보기 이전 1 ··· 248 249 250 251 252 253 다음