목록2022/02/24 (1)
Developer_Neo
[알고리즘] 최소 신장트리 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)
Spanning Tree란 (최소 연결 부분 그래프)(신장트리) 그래프 내의 모든 정점을 연결하되 사이클이 없는 그래프를 의미한다. 최소 연결이라는 것은 간선의 수가 가장 적다라는 것이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 따라서 모든 노드를 포함한 것이 서로 연결되어있어야하고 사이클이 존재하지 않는 것이다. Minimum Spanning Tree(최소 신장 트리) - MST 라고 불리고 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭한다. - 가장 가중치가 낮은 간선부터 선택을 하여 사이클이 없도록 만들면 ..
카테고리 없음
2022. 2. 24. 22:48