'''Minimum Spanning Tree generation (SVG) for Prim's algorithm.Firstly use this code to generate SVG frames.Then transform to bitmaps and convert to GIF.'''# range sizeN=300margin=20defnorm(x,y):return(x*x+y*y)**.5defsaveToSVG(nFrames,points,firmed,trying):f=open('demo_'+'0'*(3-len(str(nFrames)))+str(nFrames)+'.svg','w')f.write("<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n")forpinpoints:f.write("<circle cx=\""+str(p[0]+margin)+"\" cy=\""+str(N-p[1]+margin)+"\" r=\"5\" fill=\"white\" stroke=\"black\"/>\n")forLinfirmed:f.write("<line x1=\""+str(L[0][0]+margin)+"\" y1=\""+str(N-L[0][1]+margin)+"\" x2=\""+str(L[1][0]+margin)+"\" y2=\""+str(N-L[1][1]+margin)+"\" stroke=\"red\" stroke-width=\"5\"/>\n")forLintrying:f.write("<line x1=\""+str(L[0][0]+margin)+"\" y1=\""+str(N-L[0][1]+margin)+"\" x2=\""+str(L[1][0]+margin)+"\" y2=\""+str(N-L[1][1]+margin)+"\" stroke=\"blue\" stroke-width=\"5\"/>\n")f.write("</svg>\n")f.close()defgeneratePoints(n):importrandomasrr.seed(100)res=[]foriinrange(n):pt=[r.randint(0,N)for_in[0,1]]if[pt]notinres:res+=[pt]returnresdefprim(n,points):n=len(points)mst=[]S=set()importheapqheap=[]nframe=0whilelen(mst)<n-1:iflen(S)==0:topV=0else:whileheap[0][2]inS:heapq.heappop(heap)topV=heap[0][2]saveToSVG(nframe,points,mst,[[points[heap[0][1]],points[heap[0][2]]]])nframe+=1mst.append([points[heap[0][1]],points[topV]])heapq.heappop(heap)saveToSVG(nframe,points,mst,[])nframe+=1S.add(topV)foriinrange(n):ifinotinS:L=norm(points[i][0]-points[topV][0],points[i][1]-points[topV][1])heapq.heappush(heap,[L,topV,i])returnmst# test 30 points temporarilyn=30pts=generatePoints(n)prim(n,pts)