![](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbx1Ceq%2FbtrFaLbyFS4%2Fjc3hwG0qR5DpcKTifIF04k%2Fimg.png)
[자료구조] 그래프 - 최소 신장 트리(MST)와 최단경로
·
CS/자료구조
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 위의 그림을 살펴보면 신장트리는 그래프의 최소 연결 부분 그래프..