신장 트리(Spanning Tree) 그래프의 모든 노드(node)를 연결하면서 사이클이 없는 부분 그래프. 노드가 n개 이면, 신장 트리의 간선(edge)의 수는 n - 1개이다. 최소 신장 트리(Minimum Spanning Tree) 각 간선(edge)이 가지고 있는 가중치의 합이 최소가 되는 신장 트리. 대표적인 알고리즘으로는 프림 알고리즘(Prim's Algorithm)과 크루스칼 알고리즘(Kruskal's Algorithm)이 있다.
최소 신장 트리(MST, Minimum Spanning Tree)
신장 트리(Spanning Tree) 그래프의 모든 노드(node)를 연결하면서 사이클이 없는 부분 그래프. 노드가 n개 이면, 신장 트리의 간선(edge)의 수는 n - 1개이다. 최소 신장 트리(Minimum Spanning Tree) 각 간선(edge)이 가지고 있는 가중치의 합이 최소가 되는 신장 트리. 대표적인 알고리즘으로는 프림 알고리즘(Prim's Algorithm)과 크루스칼 알고리즘(Kruskal's Algorithm)이 있다.
2023.01.27