신장 트리, 크루스칼 알고리즘
📌신장 트리하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재 하지 않는 부분 그래프 📌크루스칼 알고리즘최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘대표적인 최소 신장 트리 알고리즘이 크루스칼 알고리즘 가장 적은 비용으로 모든 노드 연결모든 간선에 대하여 정렬을 수행한 후 가장 거리가 짧은 간선부터 집합에 포함 1. 간선 데이터를 비용에 따라 오름차순 정렬2. 간선을 하나씩 확인하며 현재의 간선이 사이클 발생시키는지 확인 - 사이클 발생하지 않는 경우 최소 신장 트리에 포함 - 사이클 발생하는 경우 최소 신장 트리에 포함시키지 않음3. 모든 간선에 대하여 2번 과정 반복 📌코드# 특정 원소가 속한 집합 찾기def find_parent(..
코딩테스트
2024. 11. 11. 19:22