2020.06.08
Union-Find 알고리즘(서로소 집합 알고리즘)
*Union-Find 알고리즘 - Disjoint-Set(서로소 집합) 알고리즘이라고 불린다. - 지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 검사하는 알고리즘.- 간선의 양끝 정점이 서로 다른 집합에 속하는 경우, 두 정점을 연결하여도 사이클이 형성되지 않는다.- Kruskal MST 알고리즘을 구현하는데 사용된다. #include #define MAX_VERTICES 100 int parent[MAX_VERTICES]; // 부모 노드int num[MAX_VERTICES]; // 각 집합의 크기 // 초기화void set_init(int n) { int i; for (i = 0; i < n; i++) { parent[i] = -1; num[i] = 1; }} // vertex가..
