MST1 [그래프 알고리즘] 크루스칼 알고리즘 Kruskal Algorithm 그래프 알고리즘이란, 그래프와 같은 복잡하고 연결성이 높은 자료구조에서순회 (Graph Traversal), 탐색 및 검색 (Graph Search) 등과 같은 목적으로 사용되는 알고리즘이다. 신장 트리란, 그래프 내의 모든 정점을 포함하는 트리로, 최소의 간선으로 모든 정점이 연결되어 있는 순환성이 없는 부분 그래프이다. 최소 신장 트리 알고리즘이란,최소 신장 트리란 그래프 내의 여러 신장 트리 중 가중치가 최소가 되는 신장 트리를 말하며, 최소 신장 트리 알고리즘은 그래프 내의 최소 신장 트리를 찾는 알고리즘이다.각 엣지에 가중치가 부여된 무방향 그래프에서 만들어지는 신장 트리중 가중치의 합이 가장 작은 신장 트리를 특별히 최소 비용 신장 트리(minimum cost spanning tree)라고 .. 2024. 8. 5. 이전 1 다음
