목록2023/10/06 (1)
Rootable의 개발일기
최소 신장 트리(Minimum Spanning Tree)
그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 📌 특징 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다. 최소 신장 트리를 만드는 알고리즘으로 크루스칼과 프림이 있다. 📌 크루스칼(Kruskal) 알고리즘 최소 신장 트리를 만드는 알고리즘(Union-Find 이용) 🔎 에지 리스트(Edge List) 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다. 클래스는 일반적으로 출발, 도착 노드와 가중치 변수로 구성된다. class Edge { int start; int end; int weight; public E..
알고리즘
2023. 10. 6. 16:37