알고리즘, 자료구조/크루스칼 알고리즘1 크루스칼 알고리즘(Kruskal Algorithm) [Python / 파이썬] 1. 크루스칼 알고리즘 신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 우리는 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다. 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. 2개의 도시 A, B를 선택했을 때, 도시 A에서 도시 B로 이동하는 경로가 반드시 존재하도록 도로를 설치하고자 한다. 모든 도시를 '연결'할 때, 최소한의 비용으로 연결 하려면 어떤 알고리즘을 이용해야 할까? 예를들어 위와같은 그래프가 있다고 가정해보자. 3개의 도시가 있고, 각 도시 간 도로를 건설하는 비용은 23, 13, 25이다. 여기서.. 2022. 1. 15. 이전 1 다음
