path compression1 Advanced Algorithm - MST(Union-Find Algorithm)(2) * 본 포스팅은 이전 포스팅과 이어지는 내용입니다. [복습] 최소신장트리(MST)의 개념 - 어떤 그래프를 기반으로 만들어진, 간선의 총 가중치(비용)가 최소이며 사이클 없이 모든 노드가 연결된 트리 최소신장트리의 대표 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 크루스칼 알고리즘 - 어떤 그래프를 기반으로 MST를 만들기 위한 알고리즘 - 모든 간선의 가중치를 오름차순으로 정렬하고 가중치가 낮은 간선부터 사이클이 생기지 않는 조건하에 모든 노드를 연결 - 사이클의 발생유무를 판단하기 위해서 크루스칼 알고리즘에서는 Union-Find 알고리즘을 사용한다. Union-Find 알고리즘 - 크루스칼 알고리즘에서 노드간의 연결을 통해 발생.. 2020. 9. 30. 이전 1 다음
