justgo_developer

prim의 알고리즘- 임의의 노드를 출발노드로 선택- 출발 노드를 포함하는 트리를 점점 키워 감- 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택 가중치가 최소인 에지 찾기- VA: 이미 트리에 포함된 노드들- VA에 아직 속하지 않은 각 노드 v에 대해서 다음과 같은 값을 유지- key(v) : 이미 VA에 속한 노드와 자신을 연결하는 에지들 중 가중치가 최소인 에지(u,v)의 가중치- ㅠ(v) : 그 에지 (u,v)의 끝점 u r:출발점 key값이 최소인 노드 찾기- 최소 우선순위 큐를 사용: V-VA에 속한 노드들을 저장: Extract-Min : key값이 최소인 노드를 삭제하고 반환

서로소인 집합들의 표현- 각 집합을 하나의 트리로 표현배열 parent를 만들어 모든 트리를 하나의 배열로 표현 -자신이 속한 트리의 루트를 찾음FIND-SET(x)if x≠p[x]then p[x]

Kruskal의 알고리즘 - 에지들을 가중치의 오름차순으로 정렬한다.- 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클을 형성하면 선택하지 않는다.- n-1개의 에지가 선택되면 종료한다.노드가 9개이므로 에지가 8개까지만 하면 된다. 더하면 어짜피 사이클이 생김. ◆ 사이클 검사- 초기 상태 : 선택된 에지 없음- 각각의 연결요소를 하나의 집합으로 표현{a} {b} {c} {d} {e} {f} {g} {h} {i} MST-KRUSKAL(G, w)A

최소비용 신장 트리(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에 대해서 안전하..