0.2 그래프(서로소 집합, MST, 최단 경로)

algorithm day12 그래프(서로소 집합, MST, 최단 경로) 0.2.1 서로소 집합들 개념 서로소 or 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합들 즉, 교집합이 없다. 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분, 이를 대표자라 한다. 표현하는 방법 연결 리스트 트리 상호 배타 집합 연산 Make-Set(x) Find-Set(x) Union(x,y) 연결 리스트 같은 집합의 원소들은 하나의 연결 리스트로 관리 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다. 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. Make-Set(x) 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산 def make_set(x): p[x] = x Find-Set(x) x를 포함하는 집합을 찾는 연산 # 재귀를 이용한 방법 def find_set(x):...

원문링크 : 0.2 그래프(서로소 집합, MST, 최단 경로)