Prim算法的正确M Let T be the output of Prim's alg edgest,12,..,t1,as the order the forl≤i≤n-l,andT=p. It can be proved that each T;is co Assume that T is containedin a MST T",thenT". IfT,then T)containsa cycle,which cannot wholy be in T. Lets,be the edge with smallest index that is not in T.Exactly one of the verticesof s,must be in T,which means that whent was chosen,s,availableas well.So,has no larger weight than s So, (T-(s))is a MST containingT Prim 算法的正确性 ( ' { } ) { }is a MST containing . chosen, availablea s well.So, has no larger weight than .So, of the verticesof must be in , which means that when was Let be the edge with smallest index that is not in .Exactly one be in . If ', then ' { }containsa cycle, which cannot wholly Assume that is containedin a MST ', then { , ,..., } '. It can be proved that each is containedin a MST. for 1 1, and . edges , ,..., , a s the order theyare selected. { , ,..., } Let T be the output of Prim's algorithm, and T contains 1 1 1 1 1 1 1 2 0 1 2 1 1 2                  l k k l k l l k k l k k k k k k i n i i T s t T s t s s T t s l T T t T T t T T t t t T T i n T t t t T t t t  tk+1 s1 sl sr-1 sr