[알고리즘] 최소 스패닝 트리(MST)

목 차최소 스패닝 트리(Minimum Spanning Tree)기본 개념 및 조건위상정렬을 구현하며 배운 것들구현 방법 선행 개념: Union-Find-Algorithm 최소 스패닝 트리(Minimum Spanning Tree) 사이클(cycle)이 없으면서 연결된 노드간의 간선 가중치가 최소인 것을 구하는 알고리즘 요약하자면 그래프 내에서 가장 효율적인 연결 구조를 찾는 것이다. 알고리즘 종류 프림 알고리즘: 하나의 노드에서 시작하여, 가장 낮은 가중치를 가진 간선을 선택하면서 점진적으로 트리를 확장한다.크루스칼 알고리즘: 모든 간선을 가중치를 기준으로 정렬하고, 가장 낮은 가중치의 간선부터 추가하면서 트리를 구성한다. 중요한 포인트는 사이클이 생기지 않는 것이다. 구현 방법과 알고리즘 문제 크루스칼 ..

Algorithm 2024.01.25