[Lecture] Greedy Algorithms, Minimum Spanning Tree

Greedy Algorithm

답을 찾기 위해 선택을 반복하는 알고리즘들 중 비교적 간단한 방법으로 선택하고, 선택한 후 바꾸지 않는 알고리즘이다

selection sort도 가장 작은 숫자를 맨 앞으로 보내고 뒤돌아보지 않기 때문에 greedy이다

 

shortest path는 보통 greedy algorithm으로 문제를 해결한다 (edge weight = 비용)

노드가 n개이면, edge는 n-1개이다

shortest path는 결국 edge n-1개를 구하는 문제이다

 

Greedy Algorithm은 항상 해결 가능한 알고리즘인가?

Minimum Spanning Tree

모든 노드를 포함하는(span:덮다) 트리를 찾는데 비용이 최소화되도록(minimum) 하는 것이다

 

Prim Algorithm

1. 하나의 노드(아무 노드)를 가진 트리에서 시작한다

2. 트리에 인접한 edge들 중 가장 작은 weight을 가진 edge를 추가한다 (단, cycle x)

3. spanning tree가 될 때까지 반복한다

 

정확성

Prim Algorithm은 답을 진짜 찾을까?

Tmst을 정답인 edge들만 있는 set이라고 한다 (답이 여러개가 있다면 그 중 하나)

Tmst의 원소와 고르는 edge의 원소가 같은지 비교를 한다

Tmst에 있는걸 고른다 => step ok

Tmst에 없는걸 고른다 => step이 꼬인다 (그러나 항상 어떤 정답으로 가고있다)

 

Tmst에 없는걸 고를 경우 어떻게 해결해야할까? (e)

e를 포함하는 사이클이 전부 빨간색은 아니다

빨간색 노드에서 검정색 노드로 넘어가는 이벤트가 e'이다

w(e) < w(e') => 정답에서 e'을 빼고 e를 넣는다는 것은 모순이다 정답보다 더 작은 답이 있다는 말이 안되기 때문이다

w(e) > w(e') => prim algorithm 특성상, 이렇게 될 수 없으므로 모순이다

w(e) = w(e') => 둘 중 아무거나 고른다 : Tmst = Tmst-{e'} U {e} (weight) 

 

 

 

구현 및 성능

priority queue를 사용한다

O(mlogn)

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

//priority queue에 triple을 넣을 것이다

class TRI {
public:
	int a, b, w; // a에서 b로 가는 edge weight w
};

class PQ {
public:
	int n; // size n
	TRI Arr[1000]; //triple array
	TRI Delete(); //TRI를 return하는 delete
	void insert(TRI x);// TRI를 insert
	PQ();
	int isEmpty(); // 비어있는지
};

PQ::PQ() {
	n = 0;
}

int PQ::isEmpty() {
	return n == 0; // n이 0이면 1을 리턴한다
}

void PQ::insert(TRI x) {
	int i;
	Arr[n+1] = x;
	i = n + 1; 
    //1~n까지 들어 있어서 n+1에 넣었음 
	n = n + 1;
	while (i > 1 && Arr[i].w < Arr[i / 2].w) {
    //i가 1보다 크고, w가 parent보다 작으면 바꾼다 / i가 1이면 맨 꼭대기에 있는 것이다
		swap(Arr[i], Arr[i / 2]);
		i = i / 2;
	}
}

TRI PQ::Delete() {
	TRI ret = Arr[1]; //return value는 Arr[1]
	int i, j;
	if (n == 1) { n = 0; return ret; }
	Arr[1] = Arr[n]; // 1에다가 n을 넣는다

	i = 1; n = n - 1;
	while (1) { 
		if (i * 2 > n) { 
			break; // 없다는 뜻
		}
		else if (i * 2 + 1 > n) { //왼쪽 child만 있는 것이다
			if (Arr[i * 2].w < Arr[i].w)//같은 경우는 어디에 있어도 상관 없다, 부모보다 자식이 더 작으면 바꿔준다
			{
				swap(Arr[i * 2], Arr[i]);
				i = i * 2;
			}
			else {
				break;
			}
		}
		else {//왼쪽과 오른쪽 child가 존재한다, j가 둘 중에 작은 것이다
			if (Arr[i].w > Arr[i*2].w && Arr[i].w > Arr[i * 2+1].w) { 
            // 두 자식이 부모보다 작을 때
				if (Arr[i * 2].w < Arr[i * 2 + 1].w) {
					j = i * 2;
				}
				else {
					j = i * 2 + 1;
				}
				swap(Arr[i], Arr[j]);
				i = j;
			}
			else if (Arr[i].w > Arr[i * 2].w && Arr[i].w <= Arr[i * 2 + 1].w) {
            //왼쪽과 바꾼다
				j = i * 2;
				swap(Arr[i], Arr[j]);
				i = j;

			}
			else if (Arr[i].w <= Arr[i * 2].w && Arr[i].w > Arr[i * 2 + 1].w) {
				j = i * 2+1;
				swap(Arr[i], Arr[j]);
				i = j;
			}
			else {
				break; // 왜 break이지?
			}
		}
	}
	return ret;
}

PQ Q;
int n,m; // 노드가 1번부터 n까지
vector<pair<int, int>> Edges[1000]; 
// (노드 개수가 1000개 들어갈 수 있다) edge[i]는 i번 노드에 붙어있는 edge들의 벡터
int M[1000]; // 현재노드 mark

int main(void) {
	
	int c, i, a, b, w;
	TRI x, y;
	scanf_s("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		scanf_s("%d %d %d", &a, &b, &w);
		Edges[a].push_back(make_pair(b, w));
		Edges[b].push_back(make_pair(a, w));
	}

	c = 1; // i는 current node
	//현재 노드에 모든 edge들을 넣는다
	M[c] = 1;
	for (i = 0; i < Edges[c].size(); i++) { 
		x.a = c;
		x.b = Edges[c][i].first;
		x.w = Edges[c][i].second;
		Q.insert(x);
	}
	while (Q.isEmpty() == 0) { // 그다음에 edge를 꺼낸다
		y = Q.Delete();
		printf("Delete %d %d %d\n", y.a, y.b, y.w);
		if (M[y.a] == 1 && M[y.b] == 1) { 
        // y.a를 marking한 후 집어넣었기 때문에 y.b만 봐도 되는 상황이다
			continue; // cycle만들기 때문에 넘어가는 것
		}
		else {
			printf("Edge from Node %d to Node %d of Weight %d Selected\n", y.a, y.b, y.w);
			c = y.b; M[c] = 1;
			for (i = 0; i < Edges[c].size(); i++) { //c에 있는 주변 노드를 Q에 넣는다
				x.a = c;
				x.b = Edges[c][i].first; 
				x.w = Edges[c][i].second;
				Q.insert(x); 
			}
		}

	}
	return 0;
}

 

prim algorithm에서 답이 단 한개 있어야 하기 위해선 어떻게 해야할까?

: edge weight가 다 달라야한다 (충분조건)

prim은 어떤 답이든지 만들 수 있다 => prim은 답이 1개 밖에 없다

답이 여러개 나올 경우에 영향을 끼치는 것 : weight이 같을 때, 시작점에 따라

 

답을 다 만들 수 있다고 생각할 수 있는데, 못만드는 답이 있을 수 있다

ex) Sort 문제에 Stable Sort(중복 순서 그대로 유지)를 가지고 풀 때

또한, weight이 같아도 답이 하나 있을 수 있다

 

증명

어떤 Tmst 정답을 고정한다 

prim algorithm을 찾을 수 있는 (Tmst에 없는) e'이 있다고 했을 때, w(e) = w(e')이므로 e'을 넣어도 prim algorithm으로 어떤 답이든 찾을 수 있다

즉, 무엇을 찍더라도 답인 곳으로 가는게 있을 땐 weight이 같을 때 뿐이라는 것이다

따라서, 답이 하나있어야하기 위해선, weigh이 다 달라야한다

---

Kruskal Algorithm

전체 그래프에서 가장 작은 edge를 추가한다 (사이클 X)

kruskal에서 사이클을 어떻게 판단할 것인가?

 

덩어리 - connected component

한 덩어리 안에서 edge를 붙이려고 하면 => cycle

서로 다른 덩어리끼리 edge를 붙이려고 하면 => uncycle

(서로 다른 덩어리끼리 edge를 붙일수록, 덩어리의 개수가 줄어든다)

두 edge의 양쪽이 덩어리인지, 아닌지에 따라 사이클 유무를 체크할 수 있다

 

정확성

Tmst을 정답인 edge들만 있는 set이라고 한다 (답이 여러개가 있다면 그 중 하나)

w(e) < w(e') => 정답에서 e'을 빼고 e를 넣는다는 것은 모순이다 정답보다 더 작은 답이 있다는 말이 안되기 때문이다

w(e) > w(e') => prim algorithm 특성상, 이렇게 될 수 없으므로 모순이다

w(e) = w(e') => 둘 중 아무거나 고른다 : Tmst = Tmst-{e'} U {e} (weight) 

 

구현 및 성능

T = 마지막 답까지 들어간다

E에서 가장 작은 weigh인 edge e를 선택할 땐, sorting한다(log n)

마지막 문장은 어떻게 할건지에 따라 O(n)이 다르다

같은 덩어리인지 아닌지 Union Find를 사용해 비교한다 

처음엔 각각 혼자 대장이다 / 해당 덩어리의 대장이 누군지 알려준다

O(mlogm)이다