728x90 최소신장그래프1 크러스컬 알고리즘(KruskalMST) □ 크러스컬 알고리즘은 최소비용 생성나무(spanning tree 스패닝 트리)를 찾는 알고리즘이다. (생성나무란 그래프 이론에서 모든 꼭짓점을 포함하는 부분 나무이다.) 크러스컬의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클(cycle)을 포함하지 않는다는 조건에 근거하여, 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택. □ 크러스컬 알고리즘의 순서 - 먼저, 그래프의 각 간선(edge)들을 가중치의 오름차순으로 정렬. - 정렬된 간선들의 리스트에서 싸이클을 형성하지 않는 간선을 찾아 최소비용신장 트리(MST)의 집합에 추가 - 만약 사이클을 형성하면 그 간선은 버린다. □ 시간 복잡도KruskalMST(G)입력 : 가중치 그래프 G=(V,E), |V|=n,.. 2016. 9. 29. 이전 1 다음 728x90
