MST (1) 썸네일형 리스트형 [알고리즘] 신장 트리, Kruskal 알고리즘 Spanning Tree 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 즉 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 신장트리는 코딩테스트에서 그리디 알고리즘 문제로 자주 출제되는 유형 중 하나라고 한다. 위 그림은 신장트리의 예시이며 모든 정점을 포함하면서 사이클이 존재하지 않는 구조를 띄고 있다. DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있으며 여러모양의 신장트리가 존재할 수 있다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 n-1개의 간전으로 연결하여야 한다. 신장트리는 일반적으로 통신 네트워크를 구축할때 사용되기도 한다. Kruskal 알고리즘 신장트리에서 간선들의 가중치 합이 최소인 트리를 말한다. Minimum Spanning Tree .. 이전 1 다음
