최소신장트리
[Graph] Prim Algorithm (프림 알고리즘)
프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 O(ElogV)의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 프림 알고리즘은 아래의 순서대로 작동한다: 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다. 그래프의 모든 변이 들어 있는 집합을 만든다. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다. 알..
[Graph] Kruskal’s algorithm (크루스칼 알고리즘)
크러스컬 알고리즘(Kruskal’s algorithm)은 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 O(ElogV) 의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 크러스컬 알고리즘은 아래의 순서대로 작동한다. 그래프의 각 꼭짓점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F 을 만든다. 모든 변을 원소로 갖는 집합 S 를 만든다. S가 비어있지 않는 동안 가장 작은 가중치의 변을 S 에서 하나 빼낸다. 그 변이 어떤 두 개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다. 그렇지 않다면 그 변은 버린다. 알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 신장 부분 그래..