목록최소비용신장트리 (1)

justgo_developer

최소비용신장트리(minimum spanning tree)-1

최소비용 신장 트리(MST) -입력 : n개의 도시, 도시와 도시를 연결하는 도로비용-문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다. - 무방향 가중치 그래프 G=(V,E)- 각 에지 (u,v)∈E에 대해서 가중치 w(u,v)- 문제 : 다음과 같은 조건을 만족하는 에지들의 부분집합 T⊆E를 찾아라.1. T에 속한 에지들에 의해 그래프의 모든 정점들이 서로 연결된다.2. 가중치의 합이 최소가 된다. 싸이클이 없는 연결된 무방향그래프를 트리라고 부른다.MST 문제의 답은 항상 트리가 됨.노드가 n개인 트리는 항상 n-1개의 에지를 가짐 Generic MST 알고리즘- 어떤 MST의 부분집합 A에 대해서 A∪{(u,v)}도 역시 어떤 MST의 부분집합이 될경우 에지(u,v)는 A에 대해서 안전하..
IT/알고리즘 2018. 1. 4. 14:45
이전 Prev 1 Next 다음