자료구조

[자료구조] 신장 트리 (Spanning Tree : ST) 와 최소 비용 신장 트리 (Minimum Cost Spanning Tree : MST)

Seunghyun_KO 2022. 1. 29. 09:00
728x90
반응형

신장 트리(Spanning Tree : ST)

 - n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리

깊이 우선 신장 트리(Depth First Spanning Tree) / 너비 우선 신장 트리(Breadth First Spanning Tree)


최소 비용 신장 트리(Minimum Cost Spanning Tree : MST)

 - 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

 - 최소 비용 신장 트리를 만드는 알고리즘

    ㄴ Kruskal 알고리즘 [알고리즘] 크루스칼 알고리즘(Kruskal Algorithm) - JAVA / 자바

    ㄴ Prime 알고리즘 [알고리즘] 프림 알고리즘(Prim Algorithm) - JAVA / 자바

728x90
반응형

'자료구조' 카테고리의 다른 글

[자료구조] 검색 (Search)  (0) 2022.02.05
[자료구조] 정렬 (Sort)  (0) 2022.01.30
[자료구조] 그래프(Graph) 순회  (0) 2022.01.23
[자료구조] 그래프(Graph)의 구현  (0) 2022.01.23
[자료구조] 힙(히프) Heap  (0) 2022.01.22