tóng-àn:PrimAlgDemo.gif
Lohankhapedia (自由的百科全書) 欲共你講..。
跳至導覽
跳至搜尋
PrimAlgDemo.gif (314 × 323 像素,檔案佔量: 248 KB,MIME類型: image/gif, 循環, 58 畫格, 29 s)
這是對Wikimedia Commons引來的一份檔案。伊佇hia ê kì-su̍t-ia̍h頂面的資訊顯示對下底. |
Khài-iàu
Soat-bêngPrimAlgDemo.gif |
English: A demo for Prim's algorithm to find minimum spanning tree on a 2D plane. |
Ji̍t-kî | |
Chhut-chhù | Ka-tī chò--ê |
Chok-chiá | Shiyu Ji |
Python 3 Code
'''
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 size
N = 300
margin = 20
def norm(x, y):
return (x*x+y*y)**.5
def saveToSVG(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")
for p in points:
f.write("<circle cx=\"" +str(p[0]+margin)+ "\" cy=\""+ str(N-p[1]+margin) +"\" r=\"5\" fill=\"white\" stroke=\"black\"/>\n")
for L in firmed:
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")
for L in trying:
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()
def generatePoints(n):
import random as r
r.seed(100)
res = []
for i in range(n):
pt = [r.randint(0,N) for _ in [0, 1]]
if [pt] not in res:
res += [pt]
return res
def prim(n, points):
n = len(points)
mst = []
S = set()
import heapq
heap = []
nframe = 0
while len(mst)<n-1:
if len(S)==0:
topV = 0
else:
while heap[0][2] in S:
heapq.heappop(heap)
topV = heap[0][2]
saveToSVG(nframe, points, mst, [[points[heap[0][1]], points[heap[0][2]]]])
nframe+=1
mst.append([points[heap[0][1]], points[topV]])
heapq.heappop(heap)
saveToSVG(nframe, points, mst, [])
nframe+=1
S.add(topV)
for i in range(n):
if i not in S:
L = norm(points[i][0]-points[topV][0], points[i][1]-points[topV][1])
heapq.heappush(heap, [L, topV, i])
return mst
# test 30 points temporarily
n = 30
pts = generatePoints(n)
prim(n, pts)
Siū-khoân
我,本作品的著作權持有者,決定用以下授權條款發佈本作品:
此檔案採用創用CC 姓名標示-相同方式分享 4.0 國際授權條款。
- 你會使自由:
- 分享 – kho͘-pih, hoat-pò͘ kap thoân-pò͘ pún chok
- 重新修改 – kái-pian pún chok-phín
- Àn i-hā ê tiâu-kiāⁿ
- 標示名姓 – 您必須指名出正確的製作者,和提供授權條款的連結,以及表示是否有對內容上做出變更。您可以用任何合理的方式來行動,但不得以任何方式表明授權條款是對您許可或是由您所使用。
- 仝款方式方享 – Lí nā kái-tōng, piàn-khoán, he̍k-chiá kun-kù pún chok chhòng-chō, lí kaⁿ-taⁿ ē-tàng ēng kap pún chok kâng-khoán he̍k-chiá saⁿ-chhiūⁿ ê hí-khó lâi hoat-pò͘ chò--chhut-lâi ê chok-phín.
在此檔案描寫的項目
描繪內容 繁體中文
授權條款 繁體中文
創用CC姓名標示-相同方式分享4.0國際 繁體中文
24 12 2016
檔案歷史
揤日期/時間,看彼時陣的檔案.
日期/ 時間 | 細張圖 | 寸尺 | 用者 | 註解 | |
---|---|---|---|---|---|
現在 | 2016年12月24日 (拜6) 20:52 | 314 × 323(248 KB) | Shiyu Ji | User created page with UploadWizard |
影像連結
以下的頁連到這个影像: