목록프림 (1)

Game Develop

크루스칼 알고리즘과 프림알고리즘의 차이.

신장 트리 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리(Minimum Spanning Tree) - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 일단 두 알고리즘 최소신장트리(MST)를 만들기 위한 알고리즘이다. 즉, 주어지는 간선의 정보로 최소의 비용을 지불해서 하나의 집합을 만드는 알고리즘이다. 크루스칼 알고리즘 크루스칼 알고리즘은 정점에 비해 간선의 개수가 적을때 MST(최소신장트리)로 만들기에 적합하다. Union-Find 알고리즘(혹은 상호배타적 집합(Disjoint-Set)알고리즘)을 선행학습해야한다. 로직은 다음과 같다. 1. parents테이블을 각자의 값으로 초기화시킨다. -> pare..
Algorithm/Algorithm 2022. 7. 9. 01:43
이전 Prev 1 Next 다음