graph=[
[0, 1, 999, 9, 999],
[1, 0, 5, 7, 3],
[999, 5, 0, 999, 4],
[9 , 7, 999, 0, 3],
[999, 1, 999, 9, 999]
]
for i in range(0,5):
print graph[i]
points =[‘A‘, ‘B‘, ‘C‘, ‘D‘, ‘E‘]
selected =[]
def is_not_selected(i):
if i in selected:
return False
else:
return True
edges = []
#1 find the shortest edge
#2 add the points of edge into selected set
#3 in the selected set, add the shortest edge with one point in the selected set,while the other is not
def get_minium_tree(edges):
k=0
while k<100:
min=1000
curi = -1
curj = -1
for i in range(0,5):
for j in range(0,5):
if ((i !=j) and (is_not_selected(i) or is_not_selected(j))):
if min>graph[i][j] :
min= graph[i][j]
curi =i
curj = j
if ((curi == -1) or (curj == -1)):
break
if is_not_selected(curi):
selected.append(curi)
if is_not_selected(curj):
selected.append(curj)
edges.append([points[curi], points[curj]])
k=k+1
get_minium_tree(edges)
print edges
Dynamic Programming--minium span tree
原文：http://www.cnblogs.com/zhaodonglin/p/5440111.html