소피it블로그

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 2. 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리 3. 크루스칼 알고리즘 대표적인 최소 신장 트리 알고리즘으로, 그리디 알고리즘으로 분류된다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 사이클이 발생한 경우: 최소 신장 트리에 포함시키지 않음 사이클이 발생하지 않은 경우: 최소 신장 트리에 포함시킴 위의 과정을 모든 간선에 대하여 반복한다. 최소 신장 트리에 포함된 간선의 비용을 모두 더한 값이 최종 비용이다. 4. 파이썬 구현 # 특정 원소가 속한 집합 찾기 def fi..