Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ขั้นตอนวิธีของพริม (อังกฤษ: 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
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
khntxnwithikhxngphrim xngkvs Prim s algorithm Prim s Algorithm thukphthnaodynkkhnitsastrchux Vojtech Jarnik inpi1930 txmathuk phthnatxodynkkhxmphiwetxrchux Robert C Prim inpi1957 aela Edsger Dijkstra inpi1959 dngnn xlkxrithumnibangthicungmkeriykwa DJP Algorithm Jarnik Algorithm hrux Prim Jarnik Algorithm sungepnxlkxrithumthiichinkarhakhnad hruxnahnkkhxngtnimthxdkhamthinxythisud eracaerimcakkartha minimum spanning tree elk inkrafkxn caknncakhxyeluxk edge thi imtxkb minimum spanning tree yxy edimmatxephimiperuxy cnidkhrbthuk node sung algorithm twni ca implement khlaykb Dijkstra s Algorithm twxyangkhntxnwithikarkhxngphrimcodekhntxnwithikhxngphrimimport 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 gt 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 khntxnwithikhxngphrim import heapq from prim import prim scenario1 krafthwip Given miesnechuxmdngthikahnd When harayathisnthisudthiechuxmthuknode Then idphllphthkhux 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 krafthwipaetmikhnadthielklng Given miesnechuxmdngthikahnd When harayathisnthisudthiechuxmthuknode Then idphllphthkhux 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 immikraf Given miesnechuxmdngthikahnd When harayathisnthisudthiechuxmthuknode Then idphllphthkhuxNone def test case3 edges None nodes None mst None assert prim nodes edges mst scenario4 mikhasakn Given miesnechuxmdngthikahnd When harayathisnthisudthiechuxmthuknode Then idphllphthkhux 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 mstBig oBig o Prim s algorithm Big o o n 2logn Best case krniimmimatrix Big o o 1 Worst case krnimimatrix Big o o n 2logn http www mwit ac th jeab sheet40206 Prim pdf lingkesiy https www geeksforgeeks org greedy algorithms set 5 prims minimum spanning tree mst 2 http www mwit ac th jeab sheet40206 Prim pdf lingkesiy https en wikipedia org wiki Prim 27s algorithm