최소 신장 트리1 [알고리즘] 크루스칼 알고리즘 정의 Spanning Tree, 최소 비용 신장 트리를 O(ElogV)O(ElogV)만에 구하는 알고리즘이다. 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야함 모든 노드가 서로 연결 트리의 속성 만족 (사이클 존재하지 않음) 코드 parent = {} rank = {} def find(node): if parent[node] != node: parent[node] = find(parent[node]) return parent[node] def union(node_v, node_u): root1 = find(node_v) root2 = find(node_u) if rank[root1] > rank[root2]: parent[root2] = root1 else: parent[root1] = root.. 2020. 11. 18. 이전 1 다음 728x90 반응형