목록최소 비용 신장 트리 (1)

Dionysus

[알고리즘🧩] 그래프의 최소 비용 문제

목차💬 최소 비용 신장 트리 (Minimum Spanning Tree, MST) 💬 Prim 알고리즘💬 Kruskal 알고리즘💬 최단 경로 알고리즘 (Dijkstra)💬 최소 비용 신장 트리 (Minimum Spanning Tree, MST)더보기무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리를 의미한다.Prim 알고리즘 또는 Kruskal 알고리즘을 활용한다.💡 신장 트리란?n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n - 1개의 간선으로 이루어진 트리📌 대표적인 그래프에서의 최소 비용 문제- 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리- 두 정점 사이의 최소 비용 경로 찾기 ✅ MST 표현 예시  💬 Prim 알고리즘더..
CS 및 알고리즘 공부/알고리즘 2024. 9. 11. 11:40
이전 Prev 1 Next 다음