반응형 Kruskal1 [Kruskal Algorithm] 크루스칼 알고리즘(feat. Union-find) 크루스칼 알고리즘을 이해하기 위해서는 신장트리, 최소 신장트리에 대한 개념을 먼저 이해해야 한다. 신장트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. * 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 이렇게 서로 사이클이 발생하지 않고 모든 정점을 잇는 경로를 신장트리라고 한다. 그럼 최소신장트리(MST)란 무엇일까? 최소 신장 트리(MST)란 최소한의 비용으로 구성되는 신장 트리를 말한다. 이처럼 간선에 대한 가중치가 주어졌을 때 최소한의 가중치를 가지고 모든 정점을 잇는 트리이다. 이제 크루스칼 알고리즘에 대해 알아보겠다 크루스칼 알고리즘이란 MST를 구하는 방식 중 하나로 간선의 가중치의 합이 최솟값이 되도록.. 2021. 9. 16. 이전 1 다음
