n
개면 간선의 개수 n-1
개 가짐그래프에서 최소 신장 트리를 만드는 대표적인 알고리즘 2개가 있다. 첫 번째는 크루스칼 알고리즘, 두 번째는 프림 알고리즘이다.
그래프의 간선을 하나씩 늘리며 MST를 만든다. 간선을 늘릴 때 가중치가 최소인 간선부터 추가하는 탐욕법을 이용한다.
과정
1) 간선은 가중치를 기준으로 오름차순 정렬한다.
2) 간선을 하나씩 살핀다. 간선을 MST에 추가했을 때 MST에 사이클이 생기지 않으면 추가한다. 사이클이 생긴다면 다음 간선으로 넘어간다.
크루스칼 알고리즘에 대해 자세하게 알고 싶다면 다음 링크를 따라가면 된다.
-> 크루스칼(kruskal) 알고리즘 더 알아보기
그래프의 정점 하나씩 늘리며 MST를 만든다. 정점을 늘릴 때 정점과 연결된 간선의 가중치가 최소인 것부터 추가하는 탐욕법을 이용한다.
과정
1) 시작 정점을 고른다. 시작 정점을 MST에 추가한다.
2) 정점과 이어진 간선을 살핀다. 간선과 이어진 다음 정점이 MST에 있지 않다면 이 정점과 간선을 최소 힙에 추가한다.
3) 최소 힙에서 꺼낸 정점이 MST에 포함되어 있지 않다면 MST에 추가하고 2)를 진행한다. 만약 꺼낸 정점이 MST에 포함되어 있으면 넘어간다.
4) 최소 힙이 빌 때까지 3)을 반복한다.
프림 알고리즘에 대해 자세하게 알고 싶다면 다음 링크를 따라가면 된다.
-> 프림(Prim) 알고리즘 더 알아보기