반응형 최소스패닝트리1 프림 알고리즘 프림 알고리즘은 그래프에서 최소 스패닝 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘 중 하나이다. MST란 원래 그래프의 모든 정점을 포함하면서 사이클이 없는 트리다. 최소 스패닝 트리는 그래프의 모든 정점을 가장 적은 비용으로 연결하는 트리를 말한다. 프림 알고리즘의 동작 방식은 1. 임의의 정점을 선택하여 시작 2. 이 정점은 초기에 최소 스패닝 트리에 포함 3. 선택한 정점과 연결된 간선들 중에서 가장 가중치가 작은 간선을 선택 4. 이 간선으로 연결된 정점을 MST에 추가 5. MST에 포함된 정점들과 연결된 간선들 중에서 가장 가중치가 작은 간선을 선택 모든 정점을 MST에 포함시킵니다. 프림 알고리즘은 우선순위 큐 를 사용하여 간선들을 관리하면 효율적으로 구현할 수.. 2023. 7. 26. 이전 1 다음 반응형
