MST 검색 결과
2 개의 검색 결과가 있습니다.
알고리즘

Prim 알고리즘 자바로 구현 (백준 1197번)

2021.08.30 - [알고리즘] - Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해 Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해 Minimum Spanning Tree와 Prim 알고리즘에 대해 설명하기 전, 먼저 Spanning Tree의 정의부터 살펴보자. Spanning Tree란 그래프 중 모든 정점이 간선으로 연결되어 있고 간선 간의 싸이클이 없는 그래프를 의미 lemonlemon.tistory.com 저번 포스팅에서 프림 알고리즘에 대해 다루었다. 그래프로 설명하면 어렵지 않지만 이를 자바 코드로는 어떻게 구현할 수 있을까? 참고로 Minimum spanning tree를 코드로 구현하는 문제를 풀고 싶다면 백준 1197번을 참고하면..

2021. 8. 30. 15:21
알고리즘

Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해

Minimum Spanning Tree와 Prim 알고리즘에 대해 설명하기 전, 먼저 Spanning Tree의 정의부터 살펴보자. Spanning Tree란 그래프 중 모든 정점이 간선으로 연결되어 있고 간선 간의 싸이클이 없는 그래프를 의미한다. 여기 앞에 Minimum이 붙으면 각 간선간의 weight의 총합이 최소가 되게 연결이 되는 그래프를 뜻하는 것이다. 즉, 모든 vertex가 다 연결되도록 spanning tree를 만드는 방식이 여러 개가 있을 때 그 중 간선의 합들이 최소가 되도록 연결하는 것을 의미한다. 즉 위와 같은 그래프에서는 Minimum Spanning Tree는 아래와 같은 모양이다. 연결하는 다른 방법도 있지만 위와 같이 연결하면 총 weight가 최소가 된다. 그렇다면 위..

2021. 8. 30. 15:09