알고리즘 이론/크루스칼 알고리즘1 크루스칼 알고리즘(Kruskal's algorithm) 1. 신장 트리(Spanning Tree)의 조건 - 주어진 그래프의 모든 노드를 연결해야 한다 - 단, 노드를 연결할 때 사이클이 생겨선 안 된다 2. 최소 신장 트리 MST(Minimum Spanning Tree) - 최소 비용(간선 가중치의 합이 최소)의 Spanning Tree 3. 크루스칼 알고리즘(Kruskal's algorithm) - 간선의 비용을 기준으로 오름차순 정렬하여 비교할 노드를 선정 - 두 노드씩 최상위 노드를 탐색한 후, 서로 다를 경우 노드를 연결하는 알고리즘 - 부모 노드가 서로 다르다는 것은 연결해도 사이클이 발생하지 않는다는 것을 의미함 * 유니온-파인드(Union-Find) 알고리즘 활용 4. 시간 복잡도: O(E log E) def find(node): # path .. 2020. 10. 11. 이전 1 다음