union-find 알고리즘2 Advanced Algorithm - MST(Union-Find Algorithm)(2) * 본 포스팅은 이전 포스팅과 이어지는 내용입니다. [복습] 최소신장트리(MST)의 개념 - 어떤 그래프를 기반으로 만들어진, 간선의 총 가중치(비용)가 최소이며 사이클 없이 모든 노드가 연결된 트리 최소신장트리의 대표 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 크루스칼 알고리즘 - 어떤 그래프를 기반으로 MST를 만들기 위한 알고리즘 - 모든 간선의 가중치를 오름차순으로 정렬하고 가중치가 낮은 간선부터 사이클이 생기지 않는 조건하에 모든 노드를 연결 - 사이클의 발생유무를 판단하기 위해서 크루스칼 알고리즘에서는 Union-Find 알고리즘을 사용한다. Union-Find 알고리즘 - 크루스칼 알고리즘에서 노드간의 연결을 통해 발생.. 2020. 9. 30. Advanced Algorithm - MST(concepts of the MST)(1) 1. 신장 트리(Spanning Tree)란? - 그래프 내부의 모든 노드가 연결되어 있으며, 동시에 트리의 속성을 만족하는 그래프를 의미한다. 그래프의 모든 노드가 서로 연결되어 있다.(거리는 멀어도 접근경로가 있다.) 트리의 속성을 만족한다.(사이클이 없음) 2. 최소 신장 트리(Minimum Spanning Tree)란? - 하나의 그래프를 기반으로 파생된 신장트리 중에서, 간선의 가중치 합이 최소인 신장트리를 의미한다. - Minumun Spanning Tree의 약자로 MST라고 부른다. 3. MST 대표 알고리즘 - MST 알고리즘이란, 어떤 그래프를 가지고 MST를 구하는 방법을 의미한다. - 대표적으로 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Al.. 2020. 9. 29. 이전 1 다음
