home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมหา Minimum Spanning Tree (MST) ด้วยอัลกอริทึม Prim ใน Python

สมมติว่าเราได้รับกราฟและถูกถามให้หา "Minimum Spanning Tree" (MST) จากกราฟนั้น MST ของกราฟคือเซตย่อยของกราฟมีน้ำหนักที่ทุกจุดยอดอยู่และเชื่อมต่อกัน และไม่มีวัฏจักรในเซตย่อย MST เรียกว่า minimum เพราะน้ำหนักเส้นขอบรวมของ MST เป็นค่าต่ำสุดที่เป็นไปได้จากกราฟ ที่นี่เราใช้อัลกอริทึม Prim MST และหาผลรวมน้ำหนักเส้นขอบของ MST จากกราฟที่กำหนด

เช่น ถ้าอินพุตเป็นดังภาพ จำนวนจุดยอด (n) คือ 4 และจุดยอดเริ่มต้น (s) = 3 ผลลัพธ์จะเป็น 14 MST จากกราฟนี้จะเป็นดังภาพ น้ำหนักเส้นขอบรวมของ MST นี้คือ 14

วิธีแก้ปัญหา

  • กำหนดฟังก์ชัน mst_find() รับ G, s:
    • distance := รายการใหม่ขนาด G เริ่มต้น negative infinity
    • distance[s] := 0
    • itr := รายการใหม่ขนาด G เริ่มต้น False
    • c := 0
    • while True:
      • min_weight := infinity, m_idx := -1
      • สำหรับ i ในช่วง 0 ถึงขนาดของ G:
        • ถ้า itr[i] เท่ากับ False และ distance[i] < min_weight:
          • min_weight := distance[i], m_idx := i
      • ถ้า m_idx เท่ากับ -1: ออกจากลูป
      • c := c + min_weight
      • itr[m_idx] := True
      • สำหรับแต่ละคู่ i, j ในค่าของ G[m_idx]: distance[i] := min(distance[i], j)
    • return c
  • G := แมปใหม่ที่มี n แมปย่อย
  • สำหรับแต่ละ item ใน edges: สร้าง G ด้วยน้ำหนักต่ำสุดระหว่าง u, v
  • return mst_find(G, s)

ตัวอย่าง

def mst_find(G, s):
    distance = [float("inf")] * len(G)
    distance[s] = 0
    itr = [False] * len(G)
    c = 0
    while True:
        min_weight = float("inf")
        m_idx = -1
        for i in range(len(G)):
            if itr[i] == False:
                if distance[i] < min_weight:
                    min_weight = distance[i]
                    m_idx = i
        if m_idx == -1:
            break
        c += min_weight
        itr[m_idx] = True
        for i, j in G[m_idx].items():
            distance[i] = min(distance[i], j)
    return c

def solve(n, edges, s):
    G = {i: {} for i in range(n)}
    for item in edges:
        u = item[0]
        v = item[1]
        w = item[2]
        u -= 1
        v -= 1
        try:
            min_weight = min(G[u][v], w)
            G[u][v] = min_weight
            G[v][u] = min_weight
        except KeyError:
            G[u][v] = w
            G[v][u] = w
    return mst_find(G, s)

print(solve(4, [(1, 2, 5), (1, 3, 5), (2, 3, 7), (1, 4, 4)], 3))

อินพุต

4, [(1, 2, 5), (1, 3, 5), (2, 3, 7), (1, 4, 4)], 3

เอาต์พุต

14