알고리즘> 그래프> 최소신장트리> 크루스칼 알고리즘
2021. 8. 28.
크루스칼 알고리즘 모든 간선을 리스트에 최소값부터 나열한다. 하나씩 뽑으면서 사이클이 생기면 빼고 사이클이 안 생기면 연결한다. 사이클 확인하는 법 Union find 알고리즘을 사용 각 노드의 루트 노드를 불러와서 같으면 사이클이 생긴다는 의미 다르면 연결한다. 합치는 방법 막무가내로 합치다가 최악의 상황이 다음처럼 될 수 있음.. 루트 노드 찾는데 N개의 노드 모두를 순례할 수 있음.. 효율적으로 하기위해 다음과 같은 방법이 사용된다. Union by rank 기법 각 트리 높이를 기억하고 union 시 두 트리 높이가 다르면 작은 트리를 큰 트리에 붙인다. 높이가 다를 경우 높이가 같을 경우 링크드리스트처럼 길어지게 만드는 게 아니라 차곡차곡 쌓이게 하는 과정이다. 따라서 N개 계산되는 것을 막고 ..