일전에 포스팅했던 크루스칼 알고리즘의 진화 버전
최소 비용으로 모든 노드를 연결하는 알고리즘.
여기서 말하는 신장 트리란 하나의 그래프가 모든 노드를 포함하고 있지만 간선이 모두 존재하지 않고 사이클을 포함하지 않는 부분 그래프이다.
최소 신장 트리 알고리즘이란 사이클을 돌지 않지만, 최소 비용으로 모든 노드를 포함하는 그래프를 생각하면 된다.
요약
모든 노드를 포함
간선의 가중치가 최소
모든 노드가 간선 연결
트리의 속성 (사이클 x)
크루스칼 알고리즘
최소신장트리를 찾는 알고리즘으로서 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.
동작원리
모든 간선들의 가중치를 오름차 순으로 정렬
가중치가 가장 작은 간선을 선택
위 선택한 노드 두개를 연결하려는 간선으로 서로 연결한다.
모든 노드를 포함할 때 까지 반복
프림 알고리즘
시작 노드를 기준으로 가장 작은 간선과 연결된 정점을 선택하면서 확장시키는 알고리즘이다.
동작원리
임의로 간선을 선택하고 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 노드를 선택하여 모든 노드가 포함될 때까지 반복
크루스칼 알고리즘 / 프림 알고리즘
크루스칼은 간선 위주라면, 프림은 노드 위주
크루스칼은 간선을 기준으로 정렬하여 과정이 오래 걸림.
사이클이 존재하지 않는지 확인이 필요함
간선의 개수가 적은 경우는 크루스칼.
간선의 개수가 많은 경우는 프림.
삶을 사는 데는 단 두가지 방법이 있다. 하나는 기적이 전혀 없다고 여기는 것이고 또 다른 하나는 모든 것이 기적이라고 여기는방식이다. – 알베르트 아인슈타인
오늘한줄.