크루스칼1 신장트리, 크루스칼 알고리즘 신장트리는 그래프에서 자주보이는 유형이다. 신장트리란, 하나의 그래프가있을때 모든 노드를 포함하면서 사이클을 발생 시키지 않는 부분그래프를 뜻한다. 이처럼 신장트리에서 최소 비용으로 만들어진 신장트리를 '최소비용 신장트리' 리고하는데 이 신장트리를 구하는 대표적인 방법은 크루스칼 알고리즘이 있다. 크루스칼 알고리즘의 동작순서는 다음과 같다. 1. 간선데이터의 비용을 크기에 따라 오름 차순 정렬한다. 2. 간선을 하나씩확인하며 사이클을 발생 시키는지 확인한다. 1. 사이클이 발생하지 않는다면 최소비용 신장트리에 포함시킨다. 2. 사이클이 발생하는 경우 포함하지 않는다. 3. 모든 간선에 대하여 2 번의 과정을 반복한다. 다음은 크루스칼 알고리즘의 코드이다. #include #include #include .. 2021. 2. 26. 이전 1 다음
