오늘은 서로소집합, 사이클, 신장트리(크루스칼 알고리즘)에 대해 알아보겠다.
먼저 서로소 집합이란 공통 원소가 없는 집합을 서로소 집합이라 한다.
예를들어
a = {1, 2, 3}
b = {3, 4, 5}
일때 집합 a 와 b 는 서로소 집합이 아니다.
코딩에서도 입력값을 받아 집합을 만들고 그 값이 어느 집합에 포함되어있는지
알수있다.
이처럼 특정값 v를 입력받았을때, 먼저 v의 값을 5라고 입력한다면
0부터 5까지의 값이 자기 자신인 0~5 의 값이 부모값이 설정된다.
본인이 속한 집합을 찾기위한 재귀함수 find_parent를 입력한다.
parent에 있는 x값이 x 값이 아니면 parent[x] 로 다시 입력을 하여
자신이 어느집합이 속해있나 알수있다.
하지만 parent[i] = i값이기때문에 현재 출력값은 자기 자신이 나오기때문에
간선으로 이루어진 값 들을 합쳐주기위한 union 함수를 입력하고,
간선 e의 값인 a,b를 입력하여 union함수로 집합을 만들어줍니다.
입력값 예시
의 값을 입력했을때
원소값은
1, 2, 3, 4, 5, 6 이 되고, 이에 따른
출력 값은
가 된다. 집합과 부모테이블이 다른이유는 루트값이 다르기때문인데
간선이 {1, 4}, {2, 3}, {2, 4}, {5, 6} 으로 묶어져있고
3은 1과 같은 집합으로 이루어져 있지만 union 함수에따른 부모함수는 2 값이기때문에 3은 1집합에 속해있지만 부모함수는 2가 출력이 된다.
선형적으로 묶여있는 경우 위의 코드처럼 작성할경우 시간복잡도가 높게나온다.
시간 복잡도를 개선하기 위해선 부모노드와 루트노드를 동일하게 만들수있다.
find함수를
ef find_parent(parent, x):
if parent[x] != x:
find_parent(parent, parent[x])
return parent[x]
로 바꿔준다면
루트노드 = 부모노드 가 된다.
같은 값을 입력했을때 출력되는 루트 값 이 달라지는것을 알수있다.
신장트리란,
모든 트리가 연결되면서 사이클이 이루어지지 않는 트리를 뜻한다.
사이클이란?
1-2 1-3 2-3 과 같이 1,2,3 원소가 서로 사이클을 이루며 이어지는 걸 뜻함.
예시)
신장트리를 코드로 표현하면 다음과 같다.
먼저 서로소값을 구할때 썻던 find 와 union과 내용이 같다. 이때 find는 시간 복잡도를 최소화 하기위해 return parent[x] 값을 사용했다.
(사용근거: 신장트리는 모든 노드가 그룹에 1회씩은 속하기때문)
v, e 입력값을 받아주며 부모테이블 변수를 v + 1 개 만들어준다.
최소값으로 1회씩 연결하는 신장트리를 만들기 위해
리스트인 graph 와 최종비용값인 result 변수 생성.
입력받은 v 값을 parent에 자기자신으로 저장
{a, b}와 비용값을 입력 하고 cost, a, b순으로 graph에 삽입하고
sort문으로 비용 값 순으로 오름차순 한다.
graph에 있는 cost, a, b값을 방문하며 a 와 b가 같은 그룹(find)에 있지않다면 a,b 를 같은그룹으로(union) 만들어주며 cost의 값은 result에 저장.
위 사진은 임의의 값 에 대한 출력 값이다.
