목록2024/11/30 (1)
지우너
크루스칼(Kruskal) 알고리즘
크루스칼 알고리즘 (Kruskal Algorithm)MST를 구하는 알고리즘 중 하나 크루스칼 알고리즘을 이용하는 예시N개의 도시가 있는데, 그래프 구조로 되어 있는 길을 모두 건설할 돈이 없어서 최소한의 비용만 투자하여 모든 도시를 어떻게든 이어주려고 합니다. 관련 개념Spanning Tree: 최소한의 간선을 사용하여 모든 정점을 연결한 그래프MST(Minimum Spanning Tree): 가중치가 있을때 최소한의 비용을 사용한 Spanning Tree. 트리이기 때문에 사이클이 존재하면 안 됨.→ Union-Find를 이용하여 사이클 유무 판별 크루스칼 알고리즘 구현 방법간선들을 저장한 후가중치를 오름차순으로 정렬간선 목록(vector, list, array 등)을 순회하면서 가중치가 작은 순으..
CS/Algorithm
2024. 11. 30. 10:45