Kruskal algorithm

Union-find algorithm

#include <stdio.h>

int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	parent[x] = getParent(parent, parent[x]);
	return parent[x];
}

void unionParent(int parent[], int a, int b){
	a= getParent(parent,a);
	b= getParent(parent,b);
	if(a>b) parent[a]=b;
	else parent[b]=a;
}

int findParent(int parent[],int a, int b){
	a= getParent(parent,a);
	b= getParent(parent,b);
	if(a==b) return 1;
	else return 0;
}


int main() {

	int parent[10];

	for(int i=0; i<10;i++){
		parent[i]=i;
	}

	unionParent(parent,1,2);
	unionParent(parent,2,3);
	unionParent(parent,3,4);
	unionParent(parent,5,6);
	unionParent(parent,6,7);

	printf("1과 5는 연결? %d\n", findParent(parent,1,5) );
	
	unionParent(parent,1,5);
	
	printf("1과 5는 연결? %d", findParent(parent,1,5) );
	
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

출력:

1과 5는 연결? 0
1과 5는 연결? 1

getParent , 재귀적 logic이 이해하기 조금 까다로웠다.

 

x==parent[x] 가 될 때까지 계속 recusre(parent[x]) 를 넘겨주는 것이다.

 

ex)

 

x[4] = x[3]

x[3] = x[2]

x[2] = x[1]

 

x[1] = 1 일 때

 

int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	parent[x] = getParent(parent, parent[x]);
	return parent[x];
    }
    
    ->
    
   parent[4] = getParent(parent,parent[4])
   parent[parent[4]] = getParent(parent,parent[parent[4]])
   parent[parent[parent[4]]] = ...
   
   parent[4] = parent[3] = parent[2] = parent[1] =1
   

이런식으로 꼬리를 물면서 부모를 찾아주는 것

 

여기서 주목해야 할 부분은

 

int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
         ↓부모 값                     ↓find index
	parent[x] = getParent(parent, parent[x]);
	return parent[x];
    }

 

https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)

Kruskal algorithm

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	parent[x] = getParent(parent, parent[x]);
	return parent[x];
}

void unionParent(int parent[], int a, int b){
	a= getParent(parent,a);
	b= getParent(parent,b);
	if(a>b) parent[a]=b;
	else parent[b]=a;
}

int findParent(int parent[],int a, int b){
	a= getParent(parent,a);
	b= getParent(parent,b);
	if(a==b) return 1;
	else return 0;
}

class Edge{
	public:
		int node[2];
		int distance;
		Edge(int a,int b,int distance){
			this->node[0]=a;
			this->node[1]=b;
			this->distance=distance;
		}
		bool operator<(Edge&edge){
			return this->distance<edge.distance;
		}
};

int main() {

	int n;
	int m;
	int a1,a2,a3;
	
	cin>>n;
	cin>>m;
	
	vector<Edge> v;
	
	for(int i=0;i<m;i++){
		cin>>a1;
		cin>>a2;
		cin>>a3;
		v.push_back(Edge(a1,a2,a3));	
	}
	
	sort(v.begin(),v.end());
	
	int parent[n];

	for(int i=0; i<n;i++){
		parent[i]=i;
	}

	int sum=0;
	for(int i =0;i<v.size();i++){
		if(!findParent(parent,v[i].node[0]-1,v[i].node[1]-1)){
			sum += v[i].distance;
			unionParent(parent, v[i].node[0]-1,v[i].node[1]-1);
		}
	}

	printf("%d",sum);
	
}

 

최소 비용 신장 트리에 이용된다. 이 때 노드의 개수 -1 = 간선의 개수가 된다.

 

간선을 거리가 짧은 순서대로 포함시키는 것이 어떨까?

 

sorting -> 오름차순으로 이 때, cycle이 발생하지 않도록 생성한다. 즉 포함시키기 전에 cycle이 형성되는 지 확인해서 형성이 된다면 포함시키지 않는다.

 

Union - Find 를 이용한다

 

사이클이 발생하는 지 확인 -> find

 

if(!findParent(parent,v[i].node[0]-1,v[i].node[1]-1))

ex) v[1].node[0] -1  ( -1은 배열의 인덱스가 0부터 시작하기 때문에 빼주는 것 )

 

v[1].node[0] = 1 

v[1].node[1] = 2 라고 쳤을 때

 

첫번째 index와 2번째 index값을 비교해서 이미 연결이 돼있었다면, 시행하지 않는다.  ---> 사이클이 발생하는 지 확인하는 방법

 

if( !findParent ) == findParent 의 boolean 값이 0 이어야 도는 것. 즉 연결이 안 돼 있었어야 if 문이 도는 것 

 

발생하지 않으면 union(연결)해준다.

 

착각할 수 있는데, 현재 연결될 수 있는 값만 제시된 상태고 연결은 되지 않은 상태이다.

 

https://www.youtube.com/watch?v=LQ3JHknGy8c&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=19

 

https://blog.naver.com/ndb796/221230994142

18. 크루스칼 알고리즘(Kruskal Algorithm)