kruskal2

• 

  최소 신장 트리(MST) : 크루스칼(Kruskal) & 프림(Prim) 최소 신장 트리최소 신장 트리를 구하라라는 문장을 코딩테스트를 하면 많이 볼 수 있다.이 문장의 뜻은 간선에 비용이 있는 그래프에서 간선을 선택하여 모든 정점을 연결하였을 때, 비용의 합이 최소가 되도록 함을 의미한다.- 각 시점에서 최선의 선택을 하는 알고리즘인 그리디(Greedy) 알고리즘 부류입니다. 신장트리- 모든 정점을 연결하는 간선의 집합. 크루스칼(Kruskal) 알고리즘- 크루스칼을 이용하여 최소 신장 트리를 구하는 방법은 다음과 같습니다. 1) 간선을 오름차순으로 정렬한 다음2) 간선 하나씩 선택하며 폐로(사이클)이 생기는지 확인한 뒤,3) 생기지 않으면 간선 리스트에 추가를, 생기면 간선 리스트에 접근 금지를 한다.반복하다보면 모든 정점이 연결될 것입니다. ex) 최소 신장 트리를 만들.. CS 지식/자료구조_알고리즘 2025. 1. 15.

• MST - Kruskal MST Kruskal MST MST란, Minimum Spanning Tree의 약자로, 최소 신장 트리라는 뜻을 가진 알고리즘을 의미한다. 해당 그래프에서 모든 point들이 edge들로 연결된다고 가정했을 때, 가중치가 가장 짧은 방법을 구하는 알고리즘이다. ex) Kruskal(크루스칼) 알고리즘, Prim(프림) 알고리즘 Kruskal(크루스칼) Kruskal이란, MST의 종류 중 하나로, 모든 정점을 최소 비용으로 연결하는 방법을 구하는 알고리즘이다. 그래프의 간선들의 가중치를 오름차순으로 정렬한다. 정렬된 간선 리스트에서 사이클을 형성하지 않는 간선을 선택한다. 해당 간선을 MST의 집합에 추가한다.ex) 백준의 1197번, 1922번, 1647번... 자바로 구현한 Kruskal 알고리즘 .. CS 지식/자료구조_알고리즘 2022. 7. 4.