# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. Prim의 MST 알고리즘 시작 정점에서 출발하여 신장 트리 집합을 단계적으로 확장해 나가는 방법으로, 이전 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택한다. 아래의 그래프를 이용해 이해하며 위의 정의를 곱씹어 본다. 시작 정점을 0으로 두자. ==> 신장트리 집합: { 0 } 0의 인접 정점 중 최소 간선을 선택하자. ==> 신장트리 집합: { 0, 5 } 이 상태에서 신장트리 집합에 인접(*)한 정점을 살펴보면, 1과 4가 있다. 간선 (0,1)과 (5,4)의 가중치를 비교해보면 (5,4)가 27로서 (0,1..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 신장트리 Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 단, 아래의 3가지 조건을 모두 만족해야 한다. 모든 정점들이 연결되어 있어야 한다. 사이클 cycle 을 포함하면 안된다. 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 신장트리는 깊이우선 탐색 또는 너비우선 탐색을 하면서 사용된 간선만 모으면 만들 수 있다. 즉, 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 이러한 신장트리는 통신망 네트워크 구축 등에 사용된다. 통신망, 도로망, 유통망 등은 간선에 가중치가 부여된 네트워크이다. 이를 가장 적은 비용으로..