'''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)
Licenc
Én, e mű szerzője a művemet az alábbi licenc alatt teszem közzé:
megoszthatod – szabadon másolhatod, terjesztheted, bemutathatod és előadhatod a művet
feldolgozhatod – származékos műveket hozhatsz létre
Az alábbi feltételekkel:
Nevezd meg! – A szerzőt megfelelően fel kell tüntetned, hivatkozást kell létrehoznod a licencre és jelezned kell, ha a művön változtatást hajtottál végre. Ezt bármilyen észszerű módon megteheted, kivéve oly módon, ami azt sugallná hogy a jogosult támogat téged vagy a felhasználásod körülményeit.
Így add tovább! – Ha megváltoztatod, átalakítod, feldolgozod ezt a művet, a közreműködésedet csak az eredetivel megegyező vagy hasonló licenc alatt terjesztheted.