데브림의 블로그 포스팅 한 것들을 한 눈에 확인하고 싶다면 클릭!
👉 https://github.com/DevLimK1/tistory-map 👈
🤔포스팅을 통해 얻어갈 수 있는 지식🧐
(클릭하면 해당 제목으로 이동해요)
탐욕 알고리즘(greedy)
👉 크루스칼 알고리즘(Kruskal Algorithm)
사전에 알고 있어야 할 용어
- 노드=정점=도시 : 그래프에서 동그라미에 해당하는 부분
- 간선=거리=비용=가중치 : 그래프에서 선에 해당되는 부분
크루스칼 알고리즘이란?
- 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘
- 최소 비용 신장 트리(MST, Minimum Spanning Tree)를 만들기 위한 대표적인 알고리즘
- ex) 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결할 때 비용을 최소한으로 하고자 할 때 이용되는 알고리즘
크루스칼 알고리즘 성립 조건
- 비용(가중치)을 오름차순으로 정렬한다
- 사이클 형성하면 안된다.
- 사이클이 형성 될 경우 간선을 무시한다.
예시를 통해 크루스칼 알고리즘을 알아봅시다!
😀 부모 정점 초기화는 정점 번호 그대로 초기화 해준다. 정점 1-5 가 연결이 되었으면 부모 정점은 더 작은 수로 변경해준다. 위 예시처럼 정점 5의 부모정점은 5였는데 1로 변경
😀 2-3을 연결할 때 부모 정점은 2로 변경한다.
이전에 3-4를 연결했을 때 부모 정점이 3이였는데, 정점 3의 부모가 2로 변경되면서 4의 부모 정점도 2로 변경된다.
😀 2-5를 연결했을 때, 같은 부모 정점을 참고 하게된다. 사이클이 형성되면서 간선을 무시한다.
😀 최소비용은 연결된 그래프의 비용들을 다 합한 값이 된다.
😀 Tip → 정점 수-1 = 간선 수
Reference
댓글