언제나 휴일

7.4 크루스칼(Kruskal) 알고리즘(최소신장트리 알고리즘) 이번에는 크루스칼 알고리즘으로 최소신장트리를 만드는 방법을 알아봅시다. 프림 알고리즘은 최적의 정점을 선택하여 최소신장트리를 만드는 방법입니다. 반면 크루스칼 알고리즘은 최적의 간선을 선택하여 최소신장트리를 만드는 방법입니다. 크루스칼 알고리즘(graph:원본 그래프) 원본 그래프의 간선 집합을 복제 복제한 간선 집합을 비중 순으로 정렬 반복(선택한 간선 개수가 graph의 정점 개수-1 보다 작다면) 최적의 간선을 선택 최적의 간선은 비중이 작은 간선 중에 선택합니다. 그런데 선택한 간선을 현재까지 만들고 있는 그래프(최소신장트리)에 추가하였을 때 사이클이 발생하지 말아야 합니다. 이를 효과적으로 구현하기 위해 원본 그래프의 간선 집합을 ..

12.4.2 크루스칼 알고리즘 소스 코드다음은 앞에서 작성한 크루스칼 알고리즘 소스 코드입니다. //Edge.h#pragma once#include using namespace std;class Edge{ string vt1; string vt2; int weight;public: Edge(string vt1,string vt2,int height); bool Exist(string vt)const; bool Exist(string vt1, string vt2)const; string Other(string vt)const; void View()const; int GetWeight()const; string GetVt1()const; string GetVt2()const;}; //Edge.cpp#incl..

12.4.1 크루스칼 알고리즘 구현간선은 프림 알고리즘에서 구현한 것과 차이가 없습니다. 그래프도 대부분 비슷합니다. 여기에서는 차이가 있는 부분만 설명할게요. 이번에는 간선을 선택할 때 간선의 비중이 같을 때 그래프에 먼저 추가한 간선을 선택하게 합시다. 이를 위해 Graph에 간선을 추가하는 부분을 수정할게요.bool Graph::AddEdge(string vt1, string vt2,int weight)//간선 추가{ if(Exist(vt1)&&Exist(vt2)) { if(Exist(vt1,vt2)) { return false; } CEIter seek = edges.begin(); CEIter last = edges.end(); for( ;seek != last; ++seek) {프림 알고리즘에..