크루스칼 알고리즘 (2) 썸네일형 리스트형 Union-find 알고리즘 (Disjoint Set), 서로소 집합 Disjoint Set이란? 서로 중복되지 않은 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조라고 생각하면 된다. 흔히 서로소 집합 자료구조 라고도 한다. Union-Find 란? Union-Find는 서로소 집합을 표현할 때 사용하는 알고리즘이다. 집합을 표현하는 방법으로는 배열, 연결리스트 등을 이용할 수 있다. 그 중 가장 효율적인 트리 구조를 이용하여 구현한다. 보통 MST의 크루스칼 알고리즘에서 사용된다. 트리를 이용한 집합의 처리 - 같은 집합의 원소들은 하나의 트리로 관리한다. (자식 노드가 부모 노드를 가리킴) - 트리의 루트를 집합의 대표 원소로 삼는다. Union-Find 연산 Make-Set(x).. 알고리즘 - 최소 신장 트리(Minimum Spanning Tree), 크루스칼(Kruskal), 프림(Prim) Python 코드 최소 신장 트리 (MST) MST : Minimum Spanning Tree 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것 신장 트리 (Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프 이다. 최소 연결이란, 간선의 수가 가장 적은 것이다. Spanning Tree의 특징 - DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다 - 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. - Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. MST (Minimum Spanning Tree) 그래프에서 모든 정점을 연결하되, 사이클이 존재하지 않고 간선의.. 이전 1 다음
