크루스칼1 [Minimum Spanning Tree] 최소 신장 트리 목차1. 신장 트리2. 최소 신장 트리3. 유니온 파인드(Union - Find) 알고리즘 4. 크루스칼(Kruskal) 알고리즘 5. 백준 1197 최소 스패닝 트리 - 크루스칼 6. 프림(Prim) 알고리즘 7. 백준 1197 최소 스패닝 트리 - 프림8. 참고자료 신장 트리 신장 트리 주어진 방향성이 없는 그래프에서 부분 그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리를 의미한다.→ 무방향이면서 사이클이 없는 → 트리신장 트리는 v개의 정점을 가질때 v-1개의 정점을 가진다. (트리의 성질) 부분 그래프일부 정점과 간선만을 선택해서 구성한 새로운 그래프 신장 트리가 아닌 그래프 예시 최소 신장 트리 신장 트리 중에서 간선의 합이 최소인 트리를 의미최소 신장 트리는 동일한 그래프에서 한.. 2024. 5. 14. 이전 1 다음
