[삼성 알고리즘] 그래프 (3)

1. 최소 신장 트리

신장 트리란 임의이 그래프에 대해서 사이클이 존재하지 않으며 모든 노드를 포함하고 일부 혹은 전부의 간선을 포함한 그래프이다.

이 때 중요한 점은 사이클은 존재하지 않으며 모든 노드는 결국 간선으로 연결되어야 한다.(한 붓 그리기같은 느낌)

 

여기서 최소 신장 트리는 해당 신장 트리를 만드는데 가중치가 최소인 것을 의미하며 최대 신장 트리는 가중치가 최대인 것으로 최소 신장 트리를 만드는 프림, 크루스칼 알고리즘에 간선 선택 우선순위만 최대로 바꿔주면 구할 수 있다.

 

1. 크루스칼 알고리즘(프림보다 알고리즘 문제로 출제가능성 높음)

크루스칼 알고리즘은 모든 간선을 정렬하고 최소 가중치 간선부터 선택해서 추가하는 작업을 진행한다. 이 떄 해당 간선으로 인해 사이클이 생성되는지 체크하고 생성되지 않는다면 간선을 추가, 아니면 다음 skip하고 다음 간선으로 넘어간다.

 

이 과정을 반복하여 모든 노드를 포함하게되면 최소 신장 트리가 항상 완성된다.

 

• 유니온 파인드

각 간선을 포함할지 여부를 결정하기 위해 사이클이 생성되는지 체크하는 부분에서 어떤 알고리즘을 쓰는지가 크루스칼 알고리즘의 효율성에 치명적이 영향을 준다. 이 때 유니온 파인드 방법을 사용한다.

<유니온 파인드는 같은 그룹이면 부모를 계속 올라타서 같은 값을 가져 간선 양 끝 노드가 이미 하나의 컴포넌트인지 확인 가능하다>

 

1. 프림 알고리즘

프림 알고리즘은 임의의 시작노드로 선택한다. 그리고 선택 노드에서 이동할 수 있는 간선들을 모두 간선 그룹에 추가하고 이 중 가장 작은 가중치로 이동한다. 이렇게 새로운 노드가 포함되면 해당 노드에서 또 이동할 수 있는 간선들을 모두 간선 그룹에 추가하고 마찬가지로 최소 간선을 선택해 나아가는 방법이다.

마찬가지로 간선을 선택할 때 사이클이 만들어 지는지 체크해야 한다.

 

• 프림 알고리즘과 크루스칼 알고리즘의 효율성은 비슷하다 둘 다 효율적이나 실제적으로 알고리즘 대회에서는 크루스칼 알고리즘을 더 많이 사용 한다고 한다.

 

 

1. 소스 코드

• 크루스칼 알고리즘

#include<iostream>

#include<vector>

#include<algorithm>

#include<tuple>

using namespace std;

 

void adding(int x, int y);

int find(int x);

int area[200];

 

bool cmp(tuple<int, int, int> a, tuple<int, int, int> b) {

return get<2>(a) < get<2>(b);

}

 

int main(void) {

vector<tuple<int,int,int>> lines;

for (int i = 0; i < 200; i++) {

area[i] = i;

}

 

tuple<int, int, int> buf = make_tuple<int, int, int>(0, 1, 6);

lines.push_back(make_tuple<int, int, int>(0, 1, 6));

lines.push_back(make_tuple<int, int, int>(1, 2, 5));

lines.push_back(make_tuple<int, int, int>(2, 5, 8));

lines.push_back(make_tuple<int, int, int>(5, 1, 8));

lines.push_back(make_tuple<int, int, int>(5, 4, 11));

lines.push_back(make_tuple<int, int, int>(4, 3, 9));

lines.push_back(make_tuple<int, int, int>(4, 1, 7));

lines.push_back(make_tuple<int, int, int>(3, 1, 3));

lines.push_back(make_tuple<int, int, int>(3, 0, 4));

 

sort(lines.begin(), lines.end(), cmp);

for (int i = 0; i < lines.size(); i++) {

if (find(get<0>(lines.at(i))) == find(get<1>(lines.at(i))))

continue;

cout << get<0>(lines.at(i)) << " " << get<1>(lines.at(i)) << endl;

if (get<0>(lines.at(i)) < get<1>(lines.at(i)))

adding(get<0>(lines.at(i)), get<1>(lines.at(i)));

else

adding(get<1>(lines.at(i)), get<0>(lines.at(i)));

}

return 0;

}

 

int find(int x)

{

if (x == area[x])

{

return x;

}

else

{

int y = find(area[x]);

area[x] = y;

return y;

}

}

void adding(int x, int y)

{

x = find(x);

y = find(y);

area[y] = x;

}