크러스컬

프로그램 개요 : C 언어를 사용한 크러스컬 알고리즘(Kruskal Algorithm) 구현. 붕괴법칙을 적용하지 않은 크러스컬 알고리즘. 붕괴법칙을 적용한 크러스컬 알고리즘 프로그램 구조 및 설계: 이전 글과 이어지는 포스팅입니다. 프로그램의 구조와 설계 방법은 아래 링크에서 보실 수 있습니다. 2021.04.09 - [알고리즘] - 크러스컬 알고리즘 구현 1 (붕괴법칙을 적용하지 않은 방법) 참고로 아래 코드에서 붕괴법칙(collapsing rule)을 적용하여 문제를 해결하는 알고리즘이 있는데, 붕괴법칙이란 임의의 노드 i에 대해 find 연산을 한다고 하였을 때, 정상적으로 루트를 찾았다면 i부터 루트까지의 경로에 있는 모든 노드들을 그 루트의 자식으로 만드는 것을 말합니다. 즉, i에 대해 find 연산을 한 번 하였다면 그 이후부터는 i부터 루트까지의 경로에 있는 모든 노드들이 한 번에 자신의 루트를 찾을 수 있다는 뜻이 됩니다. ...

프로그램 개요 : C 언어를 사용한 크러스컬 알고리즘(Kruskal Algorithm) 구현. 붕괴법칙을 적용하지 않은 크러스컬 알고리즘. 붕괴법칙을 적용한 크러스컬 알고리즘 크러스컬 알고리즘에 대한 설명은 아래 링크의 이전 글에서 볼 수 있습니다. 2020.07.02 - [알고리즘] - 크러스컬(Kruskal) 알고리즘 이 글에서는 예로 주어진 그래프에 대해서 크러스컬 알고리즘으로 문제를 해결하는 방법과 코드를 작성하였습니다. 입력 가중치 그래프 : 입력 파일 : 입력 데이터 입력 데이터가 들어있는 .txt 파일입니다. [graphInf.txt 0.00MB](https://blog.kakaocdn.net/dna/9GWpl/btq2iFfdTGn/AAAAAAAAAAAAAAAAAAAAAPR1afPSYRSSngG_pTeKxCHZPt50vsapwyoi0hUqhYlq/graphInf.txt?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1788188399&allow_ip=&allow_referer=&signature=tBqiAllXzExVIgPQgq2UUYjZeLk%3D&attach=1&knm=tfile.txt) 프로그램 실행 결과 : ...

크러스컬(Kruskal) 알고리즘이란? 크러스컬 알고리즘은 최소 비용 신장 그래프를 찾는 알고리즘 입니다. 변의 개수를 E, 꼭지점의 개수를 V라고 한다면 크러스컬 알고리즘은 O(ElogV)의 시간 복잡도를 갖습니다. 크러스컬의 MST(욕심쟁이 방법) 알고리즘 간략 코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 edge_set kruskal_MST(edge_set E, int n) { sort(E); // 간선 정렬 edge_set MST_E = { }; for (i=0; i<n; i++) init_set(i); // n개의 집합(트리)을 생성 while(MST_E의 간선 수 < n - 1) { (u, v) = E의 최소 가중치 간선; E = E - {(u, v)}; if(find(u) != find(v)) // u와 v가 다른 집합(트리) 원소 { MST_E = MST_E ∪ {(u, v)}; // 간선 추가 union(u, v); // 두 집합(트리)을 합병 } } return MST_E; } - 예제 - ...