프림 알고리즘은 정점 선택을 기반으로 최소 비용의 트리를 구성한다.
구현 필요 요소
public ArrayList<edgeSet> prim() {
// 시작 정점
// 시작 정점에서 가장 최소치인 간선
// 방문 안했다면 선택
PriorityQueue<edgeSet> pq = new PriorityQueue<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(graph.indexOf(graph.get(1)));
ArrayList<edgeSet> mst = new ArrayList<>();
while (!queue.isEmpty()) {
int now = queue.poll();
visited[now] = true;
for (edgeSet set : graph.get(now)) {
if (!visited[set.v]) {
pq.add(set);
}
}
while (!pq.isEmpty()) {
edgeSet set = pq.poll();
if (!visited[set.v]) {
queue.add(set.v);
visited[set.v] = true;
mst.add(set);
break;
}
}
}
return mst;
}