이코테_CHAP10. 그래프 이론

서로소 집합 자료구조

• 서로소 집합 : 공통 원소가 없는 두 집합

• 서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
  -> union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  -> find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

  서로소 집합 계산 알고리즘
  1) union연산을 확인하여, 서로 연결된 두 노드 A,B를 확인
  -A와 B의 루트 노드 A', B'를 각각 찾는다.
  -A'를 B'의 부모 노드로 설정
  2) 모든 union연산을 처리할 때까지 1)번 과정 반복

• 경로 압축 기법 : find함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신하는 기법

def find_parent(parent, x):
	if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]

이렇게 함수를 수정하면 각 노드에 대하여 find함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 된다.
결과적으로 경로 압축 기법을 이용하게 되면, 루트 노드에 더욱 빠르게 접근할 수 있다는 점에서 시간 복잡도가 개선

• 서로소 집합을 활용한 사이클 판별 : 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용 가능

  사이클 판별 알고리즘
  1) 각 간선을 확인하며 두 노드의 루트 노드를 확인
  -루트 노드가 서로 다르다면 두 노드에 대하여 union연산을 수행
  -루트 노드가서로 같다면 사이클(Cycle)이 발생한 것
  2) 그래프에 포함되어 있는 모든 간선에 대하여 1)번 과정을 반복

크루스칼 알고리즘

• 신장트리 : 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
• 최소 신장 트리 알고리즘 : 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘
• 크루스칼 알고리즘 : 대표적인 최소 신장 트리 알고리즘
  -> 가장 적은 비용으로 모든 노드를 연결할 수 있음
  -> 그리디 알고리즘으로 분류

  크루스칼 알고리즘
  1) 간선 데이터를 비용에 따라 오름차순 정렬
  (비용이 적은 간선부터 확인)
  2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
  -사이클이 발생하지 않는 경우, 최소 신장 트리에 포함
  -사이클이 발생하는 경우, 최소 신장 트리에 포함시키지 않는다.
  3) 모든 간선에 대하여 2)번의 과정을 반복

  최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당한다.