본문 바로가기

MST

(1)

[Java] Kruskal's Algorithm 크루스칼 알고리즘 - 최소 신장 트리(MST) 최소 신장 트리 MST(Minimun Spanning Tree) - 크루스칼 알고리즘 자바 구현 🧐 최소 신장 트리 MST(Minimun Spanning Tree)란? 최소한의 가중치를 사용하여 모든 정점이 연결되어 있을 수 있게하는 기법이다. 예시) 도시들은 모두 다리로 연결되어있을 때, 모든 도시를 갈 수 있게 다리를 연결하되 최소한의 다리 길이만을 사용하는 방법 (도시가 가로등으로 다리가 전선으로 바뀔수도 있다.) 네비게이션의 최단 경로 모든 정점(node 혹은 vortex)가 연결될 수 있는 경로 중 가장 적은 가중치(여기선 거리)를 사용하는 경로 주의사항 여기서 연결이란 다른 노드를 거쳐서 가는 것을 포함한다. 간선 혹은 브랜치(노드를 이어주는 선, 거리)는 방향성을 갖지 않는다.(연결만 되어있..

이전 1 다음

728x90

티스토리툴바