普林姆演算法

普里姆演算法是圖論中的一種貪心演算法，可在一個加權連通圖中找到其最小生成樹。意即由此演算法搜尋到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點，且其所有邊的權值之和亦為最小。該演算法於1930年由捷克數學家發現；並在1957年由美國計算機科學家羅伯特·C·普里姆獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法。描述.從單一頂點開始，普里姆演算法按照以下步驟逐步擴大樹中所含頂點的數目，直到遍及連通圖的所有頂點。時間複雜度.透過鄰接矩陣圖表示的簡易實現中，找到所有最小權邊共需formula_21的執行時間。使用簡單的二叉堆與鄰接表來表示的話，普里姆演算法的執行時間則可縮減為formula_22，其中formula_23為連通圖的邊集大小，formula_24為點集大小。如果使用較為複雜的斐波那契堆，則可將執行時間進一步縮短為formula_25，這在連通圖足夠密集時，可較顯著地提高執行速度。證明.已知圖G的邊數量為numEdge, 頂點數量為numVert, prim生成的樹為T0, 最小生成樹為Tmin則有，cost(Tmin)G[V][W]; /* 更新dist[W] */parent[W] = V; /* 更新樹 */} /* while結束*/if ( VCount Nv ) /* MST中收的頂點不到|V|個 */TotalWeight = ERROR;return TotalWeight; /* 演算法執行完畢，返回最小權重和或錯誤標記 */Python語言實現.此份原始碼使用了堆最佳化from queue import PriorityQueue as priority_queuefrom math import infclass Node:def __init__(self,id,**kwargs):self.id = idself.fst = self.lst = Nonedef __iter__(self):return NodeIterator(self)def __repr__(self):return "Node(%d)"%self.idclass NodeIterator:def __init__(self,Node):self.prst = Node.fstdef __next__(self):if self.prst == None:raise StopIteration()ret = self.prstself.prst = self.prst.nxtreturn retclass Edge:def __init__(self,fr,to,**kwargs):if fr.fst == None:fr.fst = selfelse:fr.lst.nxt = selffr.lst = selfself.to = toself.nxt = Noneself.w = 1 if 'w' not in kwargs else kwargs['w']def __repr__(self):return "Edge({},{},w = {})",format(self.fr,self.to,self.w)class Graph:def __init__(self,V):self.nodecnt = Vself.nodes = [Node(i) for i in range(V)]self.edges = []def add(self,u,v,**kwargs):self.edges.append(Edge(self.nodes[u],self.nodes[v],**kwargs))def MST_prim(self,begin):prim algorithm on a graph(with heap),returns the weight sum of the treeor -1 if impossibleq = priority_queue()vis = [False for _ in range(self.nodecnt)]q.put((0,begin))ret = 0while not q.empty():prst = q.get()if vis[prst[1]]:continuevis[prst[1]] = Trueret += prst[0]for i in self.nodes[prst[1]]:if not vis[i.to.id]:q.put((i.w,i.to.id))if all(vis):return retelse:return -1Java語言實現.import java.util.ArrayList;import java.util.Iterator;import java.util.List;public class Prim {public static List();//結點集public static List();//邊集public static List();//已經 訪問過的結點public static void main(String[] args) {primTree();public static void buildGraph() {Vertex v1 = new Vertex("a");Prim.vertexList.add(v1);Vertex v2 = new Vertex("b");Prim.vertexList.add(v2);Vertex v3 = new Vertex("c");Prim.vertexList.add(v3);Vertex v4 = new Vertex("d");Prim.vertexList.add(v4);Vertex v5 = new Vertex("e");Prim.vertexList.add(v5);addEdge(v1, v2, 6);addEdge(v1, v3, 7);addEdge(v2, v3, 8);addEdge(v2, v5, 4);addEdge(v2, v4, 5);addEdge(v3, v4, 3);addEdge(v3, v5, 9);addEdge(v5, v4, 7);addEdge(v5, v1, 2);addEdge(v4, v2, 2);public static void addEdge(Vertex a, Vertex b, int w) {Edge e = new Edge(a, b, w);Prim.EdgeQueue.add(e);public static void primTree() {buildGraph();Vertex start = vertexList.get(0);newVertex.add(start);for (int n = 0; n &lt; vertexList.size() - 1; n++) {Vertex temp = new Vertex(start.key);Edge tempedge = new Edge(start, start, 1000);for (Vertex v : newVertex) {for (Edge e : EdgeQueue) {if (e.start == v &amp;&amp; !containVertex(e.end)) {if (e.key &lt; tempedge.key) {temp = e.end;tempedge = e;newVertex.add(temp);Iterator it = newVertex.iterator();while (it.hasNext()) {Vertex v = (Vertex) it.next();System.out.println(v.key);public static boolean containVertex(Vertex vte) {for (Vertex v : newVertex) {if (v.key.equals(vte.key))return true;return false;class Vertex {String key;Vertex(String key) {this.key = key;class Edge {Vertex start;Vertex end;int key;Edge(Vertex start, Vertex end, int key) {this.start = start;this.end = end;this.key = key;參考.普林演演算法與迪科斯徹演演算法的策略相似。