วิกิพีเดีย
ขั้นตอนวิธีของพริม
ขั้นตอนวิธีของพริม (อังกฤษ: Prim's algorithm)Prim's Algorithm ถูกพัฒนาโดยนักคณิตศาสตร์ชื่อ Vojtech Jarnik ในปี1930 ต่อมาถูก พัฒนาต่อโดยนักคอมพิวเตอร์ชื่อ Robert C. Prim ในปี1957 และ Edsger Dijkstra ในปี1959 ดังนั้น อัลกอริทึมนี้บางทีจึงมักเรียกว่า DJP Algorithm , Jarnik Algorithm หรือ Prim-Jarnik Algorithm ซึ่งเป็นอัลกอริทึมที่ใช้ในการหาขนาด หรือน้ำหนักของต้นไม้ทอดข้ามที่น้อยที่สุด
เราจะเริ่มจากการทำ minimum spanning tree เล็ก ๆในกราฟก่อน จากนั้นจะค่อยๆเลือก edge ที่ ไม่ต่อกับ minimum spanning tree ย่อย ๆเดิมมาต่อเพิ่มไปเรื่อย ๆ จนได้ครบทุก node ซึ่ง algorithm ตัวนี้ จะ implement คล้ายๆกับ Dijkstra's Algorithm
codeขั้นตอนวิธีของพริม
import heapq def prim(nodes,edges): if nodes==None and edges==None: return None conn = {} for u, v, w in edges: if u not in conn: conn[u] = [(w,u,v)] # print(conn[u]) else: conn[u].append((w, u, v)) # print(conn[u]) if v not in conn: conn[v] = [(w,v,u)] # print(conn[v]) else: conn[v].append((w, v, u)) # print(conn[v]) node = nodes[0] usable_edges = conn[node] heapq.heapify(usable_edges) Q = set(node) mst = [] while len(usable_edges) > 0: wt, from_node, to_node = heapq.heappop(usable_edges) if to_node not in Q: Q.add(to_node) mst.append((from_node, to_node, wt)) # print(mst) for edge in conn[to_node]: ww, uu, vv = edge if vv not in Q: heapq.heappush(usable_edges, (ww, uu, vv)) return mst testcase ขั้นตอนวิธีของพริม
import heapq from prim import prim # scenario1:กราฟทั่วไป # Given:มีเส้นเชื่อมดังที่กำหนด # When:หาระยะที่สั้นที่สุดที่เชื่อมทุกnode # Then:ได้ผลลัพธ์คือ[('A', 'D', 5),('D', 'F', 6),('A', 'B', 7),('B', 'E', 7),('E', 'C', 5),('E', 'G', 9)] def test_case1(): edges = [ ("A", "B", 7), ("A", "D", 5), ("B", "C", 8), ("B", "D", 9), ("B", "E", 7), ("C", "E", 5), ("D", "E", 15), ("D", "F", 6), ("E", "F", 8), ("E", "G", 9), ("F", "G", 11)] nodes = ["A","B","C","E","F","G"] mst=[('A', 'D', 5),('D', 'F', 6),('A', 'B', 7),('B', 'E', 7),('E', 'C', 5),('E', 'G', 9)] assert prim(nodes,edges )==mst # scenario2:กราฟทั่วไปแต่มีขนาดที่เล็กลง # Given:มีเส้นเชื่อมดังที่กำหนด # When:หาระยะที่สั้นที่สุดที่เชื่อมทุกnode # Then:ได้ผลลัพธ์คือ[ ("A", "C", 3),("A", "B", 4),("B", "D", 2)] def test_case2(): edges = [ ("A", "B", 4),("A", "C", 3),("A", "D", 5),("B", "D", 2)] nodes = ["A","B","C",] mst=[ ("A", "C", 3),("A", "B", 4),("B", "D", 2)] assert prim(nodes,edges )==mst # scenario3:ไม่มีกราฟ # Given:มีเส้นเชื่อมดังที่กำหนด # When:หาระยะที่สั้นที่สุดที่เชื่อมทุกnode # Then:ได้ผลลัพธ์คือNone def test_case3(): edges =None nodes =None mst=None assert prim(nodes,edges )==mst # scenario4:มีค่าซ้ำกัน # Given:มีเส้นเชื่อมดังที่กำหนด # When:หาระยะที่สั้นที่สุดที่เชื่อมทุกnode # Then:ได้ผลลัพธ์คือ[ ("A", "B", 2),("A", "E",2 ),("A", "C", 3),("B", "D", 4)] def test_case4(): edges =[ ("A", "B", 2), ("A", "E", 2),("A", "C", 3),("B", "D", 4), ("D", "C", 5), ("E", "C", 6)] nodes =["A","B","C","E"] mst=[ ("A", "B", 2),("A", "E",2 ),("A", "C", 3),("B", "D", 4)] assert prim(nodes,edges )==mst Big-o
Big-o Prim’s algorithm Big o=o(n^2logn) Best case กรณีไม่มีmatrix Big o=o(1) Worst case กรณีมีmatrix Big o=o(n^2logn)
- http://www.mwit.ac.th/~jeab/sheet40206/Prim.pdf
- https://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
- http://www.mwit.ac.th/~jeab/sheet40206/Prim.pdf
- https://en.wikipedia.org/wiki/Prim%27s_algorithm