목록유니온 파인드 (2)

수학과의 좌충우돌 프로그래밍

[Algorithm] Kruskal 알고리즘

Kruskal 알고리즘이란? Kruskal 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요. Spanning Tree 와 MST [Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리 Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래.. ssungkang.tistory.com 이 알고리즘은 MST 를 찾기 위해서 greedy 하게 접근합니다. greedy 하게 접근한다는 말은 현재 순간에 최적의 선택을 한다는 의미인데 최소 비용으..
알고리즘/이론 2019. 11. 5. 21:31
[Algorithm] 유니온 파인드(Union - Find)

유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. 그러기 위해 두 가지 연산이 존재합니다. Find 노드 x 가 어느 집합에 포함되어 있는지 찾는 연산 Union 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 유니온 파인드 구현 구현은 간단한 트리를 통해서 이루어집니다. parent[i] 를 i 노드의 부모 노드 라고 정의하고 초기화 해줍니다. parent[i] = i 인 경우, 루트노드 임을 의미합니다. int parent[MAX_SIZE]; for (int i=0; i
알고리즘/이론 2019. 9. 22. 21:20
Prev 1 Next

티스토리툴바