CS/자료구조
[자료구조] 그래프 - 최소 신장 트리(MST)와 최단경로
10 그래프 - 최소 신장 트리(MST)와 최단경로 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 최소 비용 신장 트리 1-1. 신장 트리란 1-2. Kruskal의 MST 알고리즘 1-3. Prim의 MST 알고리즘 최단 경로 2-1. Dijkstra 알고리즘 2-2. Floyd-Warshall 알고리즘 위상 정렬 1. 최소 비용 신장 트리 1-1. 신장 트리란? 신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 절대 사이클이 있어서는 안 된다. n개의 정점을 가지는 그래프의 신장 트리는 n-1개의 간선을 가진다. 이미지 출처: https://imgur.com/xYkNNxl 위의 그림을 살펴보면 신장트리는 그래프의 최소 연결 부분 그래프..
