-
최소 신장 트리 (Minimum Spanning Tree)자료구조 2024. 10. 1. 19:03Q. 그래프의 최소 신장 트리 (Minimum Spanning Tree) 알고리즘 중 프림 (Prim) 알고리즘과 크루스칼 (Kruskal) 알고리즘의 차이점과 사용 사례에 대해 설명해 주세요•임의의 Undirected 그래프에서, 모든 Vertex를 최소한의 Edge를 사용해 연결하는 것•이때 Cycle이 있으면 안됨 (특정 지점에서 시작해서, 길을 따라가다 보니 시작 지점으로 돌아왔다 -> Cycle)•이때 N개의 Vertex가 있다면, 임의의 신장 트리(= 최소연결트리) 는 N – 1개의 Edge를 사용했을 것•DFS, BFS 등으로 모든 Vertex(정점,노드)를 탐색하고, 그 도중에 사용된 Edge(간선)만 모으면 만들 수 있음•신장 트리는 통신망, 도로망 구축 등에 유용함아래그림)신장 트리들 중에서, 사용된 Edge들의 가중치 합이 최소인 트리를 최소 신장 트리라고 함
'자료구조' 카테고리의 다른 글
자료구조- 해시 테이블 (Hash Table) (0) 2024.09.26 정렬 알고리즘 - 버블 정렬(Bubble Sort) (0) 2024.09.15 정렬알고리즘- 삽입정렬(Insertion Sort) (0) 2024.09.15 정렬 알고리즘 - 선택정렬 selection sort (0) 2024.09.13 자료구조 - 시간복잡도 (0) 2024.09.13