一個無向圖G的最小生成樹就是由該圖的那些連接了G的所有頂點的邊構成的樹，且其總權重最低。最小生成樹存在當且僅當G是連通的。
對于任何一生成樹T，如果將一條不屬于T的邊e加進來，則產生一個圈。如果從圈中除去任意一條邊，則又恢復樹的特性。如果邊e的權值比除去的邊的值低，那么新生成的樹的值就比原生成的樹的值低。如果在建立樹T的過程中每次添加的邊在所有避免成圈的邊中值最小，那么最后得到的生成樹的值不能再改進。對于最小生成樹的貪婪算法是成立的。
在每一個步驟中都形成最小生成樹的一條邊。算法維護一個邊的集合A，保持以下的循環不變式：
在每一次循環迭代之前，A是某個最小生成樹的一個子集。
在算法的每一步中，確定一條邊(u，v)，使得它加入到A后，仍然不違反這個循環不變式，即A與{(u，v)}的并集仍然是某一個最小生成樹的子集。稱這樣的邊為A的安全邊。
根據確定安全邊的方法，有兩種最小生成樹算法：
使最小生成樹一步步成長，每一步都把一個節點當做根并往上加邊。在算法的任一時刻，都可以看到一個已添加到樹上的頂點集。每一階段，選擇一條邊(u，v)使得此條邊的權值是所有u在樹上但v不在樹上的邊的值中的最小者。對每一個頂點保留值dv和pv，dv是連接頂點v到已加入樹上的頂點集的最短邊的權，pv是導致dv改變的最后的頂點。可見Prim算法基本上和Dijkstra算法基本是一樣的，只是dv定義有所不同，在Dijkstra算法中dv是v到源點的最短邊。
一個互聯網廣播的例子：
將所有頂點加入到隊列Q中：
將A選為源點，A出隊列Q，加入到樹T中，更新B，C的d值：
最小邊為(A,B)，將B移出Q，加入到樹T中，更新CDE的d值
以此類推，得到結果：
代碼：
def Prim(G,s): path={} pre={} alist=[] for v in G: alist.append(v) path[v]=sys.maxsize pre[v]=s path[s]=0 queue=PriorityQueue(path) queue.buildHeap(alist) while queue.size>0: vertex=queue.delMin() for v in vertex.getNeighbors(): newpath=vertex.getWeight(v) if v in queue.queue and newpath<path[v]: path[v]=newpath pre[v]=vertex queue.perUp(v) return preif __name__=='__main__': g= Graph() g.addEdge('a','b',2) g.addEdge('b','a',2) g.addEdge('a','c',3) g.addEdge('c','a',3) g.addEdge('b','c',1) g.addEdge('c','b',1) g.addEdge('b','d',1) g.addEdge('d','b',1) g.addEdge('d','e',1) g.addEdge('e','d',1) g.addEdge('b','e',4) g.addEdge('e','b',4) g.addEdge('c','f',5) g.addEdge('f','c',5) g.addEdge('e','f',1) g.addEdge('f','e',1) g.addEdge('f','g',1) g.addEdge('g','f',1) u=g.getVertex('a') path=Prim(g,u) for v in path: print v.id,' after ',path[v].id輸出：a after ab after ac after bd after be after df after eg after fPrim算法是在無向圖上運行的，記住把每一條邊都加入到兩個鄰接表中。不用堆時運行時間為O(|V|2),使用二叉堆的運行時間是O(|E|log|V|)。
連續的按照最小的權選擇邊，并且在當所選的邊不產生圈時把它作為選定的邊。形式上Kruskal算法是在處理一個森林——樹的集合，該算法找出森林中連接任意兩棵樹的所有邊中，具有最小權值的邊作為安全邊。一開始，存在|V|棵單節點樹，添加邊則將兩棵樹合并為一棵樹。算法終止的時候就剩下一棵樹了，這棵樹就是最小生成樹。此算法用不相交集合的Union/Find算法確定安全邊。對于一條邊(u，v)，如果u和v在同一集合中，那么就要放棄此邊，因為他們已經連通了，再添加此邊就會形成一個圈。
選取邊時可以根據邊的權值將邊排序，然后從小到大選取邊，不過建堆是更好的想法。
class Vertex(object): def __init__(self,key): self.id=key self.adj={} self.parent=None self.rank=0 def addNeighbor(self,nbr,weight=0): self.adj[nbr]=weight def getNeighbors(self): return self.adj.keys() def getId(self): return self.id def getWeight(self,key): return self.adj[key]def Kruskal(G): elist=[] accpeted_e_list=[] for v in G: for vertex in v.getNeighbors(): e=Edge(v,vertex,v.getWeight(vertex)) elist.append(e) queue=KruskalQueue(elist) queue.buildHeap() edge_num=0 while edge_num<G.size-1: e=queue.delMin() u=e.u v=e.v uset=Find(u) vset=Find(v) if uset!=vset: accpeted_e_list.append(e) edge_num+=1 Union(uset,vset) return accpeted_e_list class Edge(object): def __init__(self,u,v,weight): self.u=u self.v=v self.weight=weightclass KruskalQueue(object): def __init__(self,elist): self.elist=elist self.size=len(self.elist) def buildHeap(self): for i in xrange(self.size/2-1,-1,-1): self.perDown(i) def delMin(self): self.elist[0],self.elist[-1]=self.elist[-1],self.elist[0] e=self.elist.pop() self.size-=1 self.perDown(0) return e def perDown(self,i): left=2*i+1 right=2*i+2 little=i if left<=self.size-1 and self.elist[i].weight>self.elist[left].weight: little=left if right<=self.size-1 and self.elist[little].weight>self.elist[right].weight: little=right if little!=i: self.elist[i],self.elist[little]=self.elist[little],self.elist[i] self.perDown(little) def perUp(self,i): if i>0 and self.elist[i].weight<self.elist[(i-1)/2].weight: self.elist[i],self.elist[(i-1)/2]=self.elist[(i-1)/2],self.elist[i] self.perUp((i-1)/2) def Find(v): if v.parent is None: return v else: v.parent=Find(v.parent) return v.parentdef Union(u,v): if u.rank<=v.rank: u.parent=v if u.rank==v.rank: v.rank+=1 else: v.parent=u if __name__=='__main__': g= Graph() g.addEdge('a','b',2) g.addEdge('a','c',3) g.addEdge('b','c',1) g.addEdge('b','d',1) g.addEdge('d','e',1) g.addEdge('b','e',4) g.addEdge('f','c',5) g.addEdge('f','e',1) g.addEdge('g','f',1) elist=Kruskal(g) for e in elist: print 'edge(%s,%s)'%(e.u.id,e.v.id)輸出：
>>> edge(b,c)edge(f,e)edge(b,d)edge(g,f)edge(d,e)edge(a,b)
算法的最壞情況是O(|E|log|E|),受堆操作控制。圖稠密的時候,E=O(V2),實際運行時間為O(ElogV)。
新聞熱點
疑難解答
