반응형 [C++로 배우는 알고리즘과 자료구조] Day 27: 최소 신장 트리 (크루스칼, 프림 알고리즘) 최소 신장 트리 (MST, Minimum Spanning Tree)최소 신장 트리(MST)는 가중치가 있는 연결된 그래프에서 모든 정점을 포함하며, 간선의 가중치 합이 최소가 되는 트리입니다. MST를 찾는 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있습니다.크루스칼 알고리즘 (Kruskal's Algorithm)크루스칼 알고리즘은 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성하는 알고리즘입니다.크루스칼 알고리즘의 시간 복잡도:(O(E \log E + E \log V)), 여기서 (E)는 간선의 수, (V)는 정점의 수입니다.크루스칼 알고리즘 구현그래프 구현 (간선 리스트 사용)#include #include #include // 간선 구조.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 8: 최소 신장 트리 (Minimum Spanning Tree) 심화 최소 신장 트리 (Minimum Spanning Tree, MST)최소 신장 트리(MST)는 가중치가 있는 연결된 무향 그래프에서 모든 정점을 포함하며, 간선의 가중치 합이 최소가 되는 트리입니다. MST를 찾는 대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있습니다.크루스칼 알고리즘 (Kruskal's Algorithm)크루스칼 알고리즘은 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성하는 알고리즘입니다.크루스칼 알고리즘의 시간 복잡도:(O(E \log E + E \log V)), 여기서 (E)는 간선의 수, (V)는 정점의 수입니다.프림 알고리즘 (Prim's Algorit.. 2024. 8. 1. 이전 1 다음 반응형
