2JINISHAPPY 2JINISHAPPY

MST는 그리디 알고리즘을 이용해서 구할 수 있는 트리의 한 형태이다. 연결 그래프(하나의 Connected Component로 이루어진 그래프)에서 생성할 수 있는 부분 그래프이기도 하다. 그래프의 형태를 한 네트워크 회선이 존재할 때, 네트워크 구축 비용을 최소로 하는 경우의 수를 찾고 싶을 때 쓰이기도 한다. 그래프 G=(V,E)와 같고, 각 edge에 weight가 주어져 있을 때, 아래의 두 조건을 만족하는 G'( V(G), T )가 MST이다. 1️⃣ G'은 Connected하다. 2️⃣ G'은 포함할 수 있는 edge들의 cost 총 합을 최소로 한다. 해당 그래프에서는 연두색으로 칠해진 edge들을 선택했을 때 모든 vertex를 포함할 수 있으면서, cost의 합을 최소로 할 수 있기 때..