ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของพริม"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
เพิ่มประวัติ |
code และอ้างอิง |
||
บรรทัด 2:
เราจะเริ่มจากการทำ minimum spanning tree เล็ก ๆในกราฟก่อน จากนั้นจะค่อยๆเลือก edge ที่ ไม่ต่อกับ minimum spanning tree ย่อย ๆเดิมมาต่อเพิ่มไปเรื่อย ๆ จนได้ครบทุก node ซึ่ง algorithm ตัวนี้ จะ implement คล้ายๆกับ Dijkstra's Algorithm
ตัวอย่างขั้นตอนวิธีการของพริม
[[ไฟล์:ขั้นตอนวิธีการของพริม.jpg|thumb|ตัวอย่างขั้นตอนวิธีการของพริม]]
==codeขั้นตอนวิธีของพริม==
เส้น 18 ⟶ 21:
conn[v] = [(w,v,u)]
else:
conn[v].append((w, v, u))
node = nodes[0]
usable_edges = conn[node]
เส้น 34 ⟶ 37:
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
อ้างอิง<blockquote><ref group="https://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/">Prim’s Minimum Spanning Tree</ref></blockquote><ref group="https://en.wikipedia.org/wiki/Prim%27s_algorithm">Prim’s algorithm</ref>
<ref group="http://www.mwit.ac.th/~jeab/sheet40206/Prim.pdf">ที่มา</ref>
[[หมวดหมู่:ขั้นตอนวิธีกราฟ]]
| |||