잡동사니

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 최소비용신장트리(Minimum Spanning Tree)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 최소비용신장트리는 무방향 가중치 그래프에서 모든 노드를 이었을 때 가중치가 가장 적은 엣지들의 부분집합을 찾는 방식입니다. 이 때, MST(Minimum Spanning Tree) 는 유일하지 않기 때문에 선별한 엣지들을 많은 MST들 중 일부인 부분집합 이라는 표현을 한다. 공학적으로는 계층적 구조의 연결을 트리(rooted tree)라고 인식하지만 수학적으로는 싸이클이 없는 연결된(connected) 무방향 그래프를 트리라고 합니다. 게다가 MST 문제에서 싸이클이라는 것은 중복 경로라는 의미로 ..