반응형 최소가중치1 크루스칼 알고리즘(kruskal Algorithm), 최소 신장 트리(MST) c++ 구현 우리는 흔히 알고리즘 문제를 풀다보면 적은 비용으로 연결! 하는 문제를 자주 접하게 되는데요. 자주는 보지는 않지만 가끔씩 보면 까먹기 마련입니다. 저도 까먹고 풀다가 어..? 크루스칼 알고리즘인데 하는 생각이 들어서 이번에 다시 기억하고자 포스팅을 하려합니다. 크루스칼 알고리즘 (Kruskal Algorithm) -> 최소신장트리(MST) 구하기 위해 사용 앞서 위에서 말씀 드린듯이 적은 비용으로 연결하는 것이 핵심입니다. 무방향으로 연결된 노드와 간선이 주어졌을때 우리는 간선의 가중치(비용)에 대해서 모든 노드가 연결이 되어야 하는데 가중치(비용)이 최소화 되는것을 찾을때 사용하게 되는 알고리즘입니다. 최소 신장 트리(MST)가 뭐야? 신장 부분 그래프 (Spanning tree)에서 사용된 간선들의.. 2023. 7. 6. 이전 1 다음 반응형
