개발하는 리프터 꽃게맨입니다.

https://powerclabman.tistory.com/90 [C++/이론] 최소 스패닝 트리 : 프림 알고리듬 (Prim Algorithm) 스패닝 트리 임의의 그래프가 있다고 생각해봅시다. 스패닝 트리란 부분 그래프 중 하나로 다음과 같은 조건을 만족해야 합니다. 1) 그래프 내의 모든 정점을 포함하는 부분 그래프 2) 사이클이 powerclabman.tistory.com 개요 크루스칼 알고리즘은 최소 스패닝 트리를 구하기 위한 또 다른 알고리즘입니다. 앞전에 소개한 프림 알고리즘과 차이점은, 프림 알고리즘의 경우 특정 노드에서 출발해 노드들을 탐색하면서 최소 스패닝 트리를 완성시켜나가는 알고리즘이었다면 크루스칼 알고리즘은 모든 경로를 두고, 최소 경로만 쏙쏙 선택해서 트리를 만들어낸다고 보면 되..

스패닝 트리 임의의 그래프가 있다고 생각해봅시다. 스패닝 트리란 부분 그래프 중 하나로 다음과 같은 조건을 만족해야 합니다. 1) 그래프 내의 모든 정점을 포함하는 부분 그래프 2) 사이클이 없는 그래프 이런 그래프를 신장 트리 (혹은 스패닝 트리)라고 합니다. 스패닝 트리를 찾는 것은 매우 단순합니다. 단순 BFS, DFS를 하면 스패닝 트리를 찾을 수 있죠. 그런데 가중치 그래프의 경우를 생각해봅시다. 모든 노드를 다 방문하는데 비용이 다 다르다면, 아무래도 최소 비용으로 방문하는 것이 가장 좋겠죠? 그래서 중요하게 다뤄지는 알고리즘이 최소 신장 트리 (최소 스패닝 트리) 이며, 이는 모든 노드를 방문하는 최소 비용의 신장트리를 찾는 것을 목적으로 합니다. 더보기 최소 비용 경로 알고리즘과 무엇이 다..