이대로 한번 코딩 해봐야겠다.
아래는 prim's graph 알고리즘에 대한 내 설계 내용
input : structure array 'tree',priority queue, table(as fringe set)
output : weight of MST
choose aux vertex a
tree.add(a);
makeheap(); // by distance from a to vertices without a
while(heap.nomore)
{
struct tempset = poptop()
tree.add(tempset)
totalweight += tempset.d
for(tree.ind = 0 -> tree.end.ind)
{
for(heap.ind = 0 -> heap.end.ind)
{
if(tree.ind.cnum == heap.ind.cnum)
{
if(tree.ind.distance < heap.ind.distance)
heap.ind.distance = tree.ind.distance
}
}
}
fixminheap();
}
print.totalweight
priority queue 에서 사용하는 배열에 대한 직접 접근이 필요하다.
최근 덧글