[자료구조] 6장 실습 kruskal, prim, sollin

최소비용 신장트리 알고리즘

minheap : 노드 키 값 < 자식 키 값 => priority queue 사용

priority_queue<Edge, vector<Edge>, Compare > PQ; 

최소비용 신장트리이므로 minheap, PQ의 top()이 최소비용임

 

알고리즘 흐름 정리

kruskal은 전체 트리 중 가장 최소 비용의 간선들만 차례로 택한다

prim은 가장 최소 비용 간선 택, 포함된 정점의 edge들 중 최소 비용 edge 택

sollin은 모든 정점들의 최소 비용 간선 택 => 연결 반복

 

 

kruskal 정의

한 번에 한 간선씩 추가

T에 포함될 간선은 가장 적은 비용 순으로 택

사이클 형성하는 간선은 제외

n-1개 간선 적용

void kruskal() {
	Sets sets(NNODES); 
	int nedges = 0; 
	while ((nedges < NNODES - 1) && !PQ.empty()) 
    {
		Edge e = PQ.top();
		PQ.pop();
        
		int root1 = sets.Find(e.v1);
		int root2 = sets.Find(e.v2);
		if (root1 != root2)
		{
			sets.WeightedUnion(root1,root2); //int i,j는 루트임
			nedges++; 
			cout << e;
		}
	}
}

간선 읽어오는 함수 정의 : ReadEdges4kruskal

void ReadEdges4kruskal(istream& is) 
{
	Edge e;
	while (GetEdge(is, e))
		PQ.push(e);
}

main()

int main(int argc, char* argv[])
{
	ifstream is;

	if (argc == 1) is.open("kin.txt");
	else is.open(argv[1]);
	if (!is) { cerr << "No such input file\n"; exit(1); }
	is >> NNODES;
	if (NNODES < 2) { cerr << "#nodes must be 2.." << endl; exit(1); }
	try {
		ReadEdges4kruskal(is);
		kruskal();
	}
	catch (char const* str)
	{
		cerr << "Exception: " << str << endl; exit(1);
	}
}

txt 파일 읽어와서 ReadEdge4lruskal()을 통해 PQ에 push

이때 compare함수를 통해 minheap이 되도록 push

큐에 다 넣었으면 kruskal함수 시작

minheap으로 정렬된 qqueue이므로 top 바로 가지고 와서 cycle 형성하는지만 확인하고 안 형성하면 weightedunion()

이때 queue에서 pop하면 PQ값 재정렬 필요하여 다시 compare함수 실행해 queue의 top에 최소비용이 들어가도록 재정렬

위 과정 반복해 최소비용 신장트리 도출 가능

 

prim 정의

한 번에 한 간선씩 추가

선택된 정점은 TV에, 선택된 간선은 T에 추가 => 새로운 간선은 현재 선택된 정점의 edge들 중 선택

 

prim은 각 정점 별로 큐를 만들어야함

priority_queue<Edge,vector<Edge>,Compare>PQ;

queue<Edge>* Q;

 

각 정점 별 q에서 q의 원소가 empty가 될 때까지 PQ로 해당 정점의 edge를 옮겨야함

void MoveIntoPQ_EdgesOfNodes(int v) {
	while   (!Q[v].empty()) //q의 원소가 empty가 될 때까지
	{
		Edge e = Q[v].front();
		PQ.push(Q[v].front());
        Q[v].pop();
	}
}

prim 함수 정의

void prim() {
	Sets sets(NNODES);
	int nedges = 0; 
	while (nedges < NNODES - 1) {
		if (PQ.empty()) throw "No Spanning Tree Exists.";
		
        Edge e = PQ.top(); 
		PQ.pop(); 
        
		int root1 = sets.Find(e.v1);
		int root2 = sets.Find(e.v2);
		// PQ 꺼낸 e가 자격이 있으면(사이클이 아니면),  
		if (root1 != root2)
		{
			//두 집합 WeightedUnion, nedges 갯수추가, e 출력
			sets.WeightedUnion(root1, root2);
			nedges++;
			cout << e;
		}
		// 트리에 연결 처리된 e의 두 점에 연결된 edge들을 PQ로 옮긴다
		MoveIntoPQ_EdgesOfNodes(e.v1);
		MoveIntoPQ_EdgesOfNodes(e.v2);
	}
}

void ReadEdges4prim(istream& is) {
	Edge e;
	Q = new queue <Edge> [NNODES];
	
    while (GetEdge(is, e))
	{
		Q[e.v1].push(e);
		Q[e.v2].push(e);
	}
	MoveIntoPQ_EdgesOfNodes(0); //시작 점 0의 edge들을 PQ로 이동한다
}

초기 각 정점마다 가지고 있는 edge들을 각각의 q에 넣어줌

초기 0에서 시작 => 0이 가지고있는 edge를 0의 q에서 PQ로 옮겨주고 시작

PQ의 top을 통해 최소비용간선 선택 => 선택된 간선의 u,v의 q를 다시 PQ로 옮겨주고

다시 PQ의 top을 통해 최소 비용 간선 선택 => 반복 n-1개 간선을 포함할 때까지

 

sollin 정의

각 단계에서 여러 간선 선택함

=> 각 정점마다 하나의 최소비용간선 택하여 union : 초기 정점 개수만큼의 PQ(minheap) 필요

prim과 다르게 여기서는 PQ의 원소들을 옮기게됨

선택된 간선은 구축 중인 신장트리에 추가하게 됨

: 오직 하나의 트리만 존재하거나 더 이상 선택할 간선이 없을 때 종료

priority_queue<Edge, vector<Edge>,Compare>* PQ;

 

각 정점 별 PQ에서 PQ로 이동

void MoveintoPQofRoot(int v2, int v1)
{
	while (!PQ[v2].empty())
	{
		Edge e = PQ[v2].top();
		PQ[v2].pop();
		PQ[v1].push(e);
	}
}

 

sollin 함수 정의

void sollin() {
	Sets sets(NNODES);
	int nedges = 0;
	
    while (nedges < NNODES - 1)
	{
		for (int i = 0; i < NNODES; i++)
		{
			//sollin은 정점이 아닌 트리가 WeightedUnion 되므로 
            //루트 v를 Find하고 최소 edge를 검색
			int v = sets.Find(i);//엣지를 priority queue에서 가져옴 
			if (PQ[v].empty())//처음에는 루트니까 0,1,2 이런게 들어가겠지.
			{
				continue; // 비어져있다면 그 다음으로 가라. 왜 비어있지? 자기 루트한테 minheap다 넘겨주기 때문에..
			}
			Edge e = PQ[v].top();
			PQ[v].pop();
			int v1_root = sets.Find(e.v1);
			int v2_root = sets.Find(e.v2);
			if (v1_root != v2_root)
			{
				sets.WeightedUnion(v1_root, v2_root);
				nedges++;
				cout << e;

				MoveintoPQofRoot(v2_root, v1_root);
			}
			// vertex 번호가 작은  PQ로 edge를 모은다
			//각 점의 pq를 루트의 pq로 옮겨 합쳐줘야함 //트리 하나로 만듦	
		}
	}
}