'''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)
Licenciranje
Ja, nosilac autorskog prava nad ovim delom, objavljujem isto pod sledećom licencom:
da delite – da umnožavate, raspodeljujete i prenosite delo
da prerađujete – da preradite delo
Pod sledećim uslovima:
autorstvo – Morate da date odgovarajuće zasluge, obezbedite vezu ka licenci i naznačite da li su izmene napravljene. Možete to uraditi na bilo koji razuman manir, ali ne na način koji predlaže da licencator odobrava vas ili vaše korišćenje.
deliti pod istim uslovima – Ako izmenite, preobrazite ili dogradite ovaj materijal, morate podeliti svoje doprinose pod istom ili kompatibilnom licencom kao original.