목록MST (1)

Expert스터디 3일차(2016.06.01)

Union Find2가지 연산이 있다.group(A): 정점 A가 속한 그룹의 대표int r[1000]; int group(int node) { if(!r[node]) return node; return r[node] = group(r[node]); }join(A, B): 정점 A가 속한 그룹과 정점의 B가 속한 그룹을 합친다.void join(int A, int B) { int ga = group(A); int gb = group(B); if(ga==gb) return; // do nothing r[ga]=gb; }Kruskal최소 신장 트리 (Minimum Spanning Tree)를 구하는 알고리즘. 간선들을 가중치 오름차순으로 정렬한 후, 첫번째 간선부터 보면서 현재 간선이 사이클을 만들지 않으면..
Algorithm/그밖에2 2016. 6. 4. 00:47
이전 Prev 1 Next 다음