컴퓨터 사이언스/자료구조와 알고리즘
2021. 4. 29. 15:33
[Greedy] 최소 신장 트리(Minimum Spanning Tree)
최소 신장 트리가 무엇인지, 그리고 최소 신장 트리를 만들기 위한 효율적인 알고리즘에 대해 알아보겠다. 1. 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리는 Weighted, Undirected Graph에서 필요한 개념이다. weighted란 각 Edge마다 가중치가 다르고, Undirected는 방향이 없다는 것이다. 방향이 없다는 것은 Vertex A에서 Vertex B로 가는 가중치와 Vertex B에서 Vertex A로 가는 가중치가 항상 같다는 것이다. 신장 트리는 그래프에서 최소한의 Edge만을 가지는 연결 부분 그래프이다. 그리고 MST(최소 신장 트리)는 신장 트리 중, weight의 합이 가장 작은 그래프를 의미한다. MST를 구하는 것은, 최단 거리를 구하는..
