개발스토리

저번 포스팅에 이어서,,, 최소 비용 신장 트리 찾기 _ 간선 지향 전략 1. 그래프에 남아 있는 가장 가중치가 작은 간선을 선택한다. 2. 선택된 간선이 합쳐진 두 개의 정점들 사이에 있다면 그 간선을 버리고 아니면 최소 비용 신장 트리에 추가. 3. (n-1)개의 간선들이 추가될 때까지 과정 1과 2를 반복한다. 예: 간선 지향 전략_크루스칼 알고리즘 1. 간선들을 가중치에 의해 정렬한다. 2. (a,b)가 가중치가 가장 작으므로 선택하여 T에 추가하고, 정점 a와 b를 합친다. 3. 남은 간선들 중 (d,e)가 가중치가 가장 작으므로 선택하여 T에 추가하고 그래프의 정점 d와 e를 합친다. 4. 남은 간선들 중 (a, e)와 (b, e)가 가중치가 가장 작으므로 임의로 (a, e)를 선택하여 T에 ..