Minimum Spanning Tree (1) 썸네일형 리스트형 최소 신장 트리 Minimum Spanning Tree, 크루스칼 Kruskal's, 프림 Prim's 알고리즘 Greedy Algorithm 각 단계에서의 최선책을 선택하여 다음 단계로 진행하는 알고리즘 현재 선택에 의해 다음 단계의 조건이 변하는 경우 부적합 최소 신장 트리 MST 모든 노드를 포함하는 그래프, 모든 노드가 연결된 그래프, 트리 속성을 만족하는 그래프 그래프 상에서 각 간선에 가중치가 부여됨 한 정점을 기준으로 가능한 가장 작은 가중치의 간선들을 사용하여 모든 정점을 연결하는 트리(MST) MST를 구하는 문제를 푸는 알고리즘 크루스칼 가장 작은 값의 간선을 선택한다. → 그 다음 작은 값의 간선을 선택한다. → 그 다음으로 작은 값의 간선을 선택하되 사이클이 생기지 않게 선택한다. → 모든 정점을 선택할 때까지 위 선택 과정을 반복한다. 프림 알고리즘 기준 정점에서 출발하는 가장 작은 값은 간.. 이전 1 다음
