tóng-àn:KruskalDemo.gif
Lohankhapedia (自由的百科全書) 欲共你講..。
跳至導覽
跳至搜尋
KruskalDemo.gif (314 × 323 像素,檔案佔量: 415 KB,MIME類型: image/gif, 循環, 93 畫格, 47 s)
這是對Wikimedia Commons引來的一份檔案。伊佇hia ê kì-su̍t-ia̍h頂面的資訊顯示對下底. |
Khài-iàu
Soat-bêngKruskalDemo.gif |
English: A demo for Kruskal'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 Kruskal'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
class Edge(object):
def __init__(self, source, target, points):
self.u = source
self.v = target
self.len = norm(points[source][0]-points[target][0], points[source][1]-points[target][1])
class UnionNode(object):
def __init__(self):
self.next = None
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 kruskal(n, points):
n = len(points)
union = [UnionNode() for _ in points]
edges = []
for i in range(n-1):
for j in range(i+1, n):
e = Edge(i, j, points)
edges.append(e)
edges.sort(key = lambda x:-x.len)
mst = []
nframe = 0
saveToSVG(nframe, points, mst, [])
nframe+=1
while len(mst)<n-1:
s = edges[-1].u
t = edges[-1].v
saveToSVG(nframe, points, mst, [[points[s], points[t]]])
nframe+=1
p = union[s]
q = union[t]
while p.next != None: p = p.next
while q.next != None: q = q.next
if p!=q:
newNode = UnionNode()
p.next = q.next = newNode
mst.append([points[s], points[t]])
saveToSVG(nframe, points, mst, [])
nframe+=1
edges.pop()
return mst
# test 30 points temporarily
n = 30
pts = generatePoints(n)
kruskal(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(415 KB) | Shiyu Ji | User created page with UploadWizard |
影像連結
以下的頁連到這个影像: