最小生成树Prim算法 Python源代码

        Python内置的数据结构是广义表，可以非常方便的表示数组，列表，复杂类型集合等，是一个真正的容器数据结构。省去了C++/Java的大量定义和操作数据结构的代码，使得代码更加简洁，更加正确，程序能够直接表述问题。不需要在不同的类型之间来回变换，传递，拷贝和赋值。

v1-v6: vertex.第一个元素是顶点，其他元素是和该顶点相连的顶点。
E: edges 所有边的集合

v1: 1->2, 1->3, 1->4
v2: 2->1, 2->3, 2->5

Prim算法的Python实现(Python2.6.5)
-----------------------------------------
#!/usr/bin/python
v1=(1,2,3,4)
v2=(2,1,3,5)
v3=(3,1,2,4,5,6)
v4=(4,1,3,6)
v5=(5,2,3,6)
v6=(6,3,4,5)
V=(v1,v2,v3,v4,v5,v6)
E=[(1,2,6),(1,3,1),(1,4,5),(2,3,5),(2,5,3),(3,4,5),(3,5,6),(3,6,4),(4,6,2),(5,6,6)]
E.sort(key=lambda d:d[2])
A=[]
PointA=[]
A.append(E[0])
PointA.append(E[0][0])
PointA.append(E[0][1])
E.pop(0)
while(1):
      for i in range(len(E)):
        e=E[i]
        if ( ((e[0] in PointA) and (e[1] in PointA)) or ((e[0] not in PointA) and (e[1] not in PointA))):
          continue
        else:
          break
      A.append(e)
      if(e[0] in PointA):
        PointA.append(e[1])
      elif(e[1] in PointA):
        PointA.append(e[0])
      E.remove(e)
      if(len(PointA)==len(V)):
        break
if(len(A) != len(E)):
  print 'No MST!!!!'
  exit
for a in A:
  print "edge sequence: %d %d, length %d" %(a[0],a[1],a[2])

>>> 运行结果
edge sequence: 1 3, length 1
edge sequence: 3 6, length 4
edge sequence: 4 6, length 2
edge sequence: 2 3, length 5
edge sequence: 2 5, length 3