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 |