ក្បួនដោះស្រាយរបស់ Prim

ក្បួនដោះស្រាយលោភដែលរកឃើញមែកធាងគ្របដណ្តប់តូចបំផុតសម្រាប់ក្រាហ្វទម្ងន់គ្មានទិសដៅ។

Visualization

Step 1 / 6

Speed:

Details

Analogy

ស្រមៃថាអ្នកត្រូវដំឡើងបណ្តាញខ្សែកាបដើម្បីតភ្ជាប់ផ្ទះច្រើននៅក្នុងសង្កាត់។ អ្នកចង់ប្រើខ្សែកាបតិចបំផុត។ ក្បួនដោះស្រាយរបស់ Prim ដូចជាការចាប់ផ្តើមនៅផ្ទះមួយ បន្ទាប់មកតភ្ជាប់វាទៅអ្នកជិតខាងជិតបំផុត។ ឥឡូវនេះ ពីបណ្តាញផ្ទះពីរនេះ អ្នករកផ្ទះបន្ទាប់ដែលជិតបំផុតទៅផ្ទះណាមួយដែលតភ្ជាប់ហើយ ហើយបន្ថែមការតភ្ជាប់នោះ។ អ្នកតែងតែបន្ថែមការតភ្ជាប់ដែលថោកបំផុតពីបណ្តាញដែលមានស្រាប់របស់អ្នកទៅផ្ទះថ្មីដែលមិនទាន់តភ្ជាប់ រហូតដល់ផ្ទះទាំងអស់ត្រូវបានតភ្ជាប់។

Purpose

ដើម្បីរកឃើញសំណុំរងនៃគែមនៃក្រាហ្វទម្ងន់គ្មានទិសដៅដែលតភ្ជាប់គ្នា ដែលតភ្ជាប់កំពូលទាំងអស់ជាមួយគ្នា គ្មានវដ្តណាមួយ និងជាមួយទម្ងន់គែមសរុបតូចបំផុត។

Use Cases

ការរចនាបណ្តាញ (ដូចជា ទូរគមនាគមន៍ ការផ្គត់ផ្គង់ទឹក បណ្តាញអគ្គិសនី) ឱ្យមានប្រសិទ្ធភាពថ្លៃដើមតាមដែលអាចធ្វើទៅបាន។ ក៏ត្រូវបានប្រើក្នុងការកំណត់ផ្លូវបណ្តាញ និងការរកផ្លូវផងដែរ។

Algorithm Steps

Line 1

initialize visited set and priority queue

add start vertex with weight 0 to queue

while queue not empty:

pop vertex with minimum weight

if vertex already visited: continue

mark vertex as visited

add edge to MST

for each neighbor of vertex:

if neighbor not visited:

add neighbor to queue with edge weight

return MST

Current

Executed

Pending

Explanation

What's Happening?

Step 1/6

ចាប់ផ្តើមនៅកំពូល A។ បន្ថែមគែមរបស់វា (A-B ទម្ងន់ 2, A-D ទម្ងន់ 6) ទៅ priority queue។

Updates with each step • Clickfor full view

Code Implementation

import heapq

def prim(graph, start_node):
    mst = []
    visited = {start_node}
    edges = [
        (weight, start_node, neighbor)
        for neighbor, weight in graph[start_node].items()
    ]
    heapq.heapify(edges)

    while edges:
        weight, u, v = heapq.heappop(edges)
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            for neighbor, weight in graph[v].items():
                if neighbor not in visited:
                    heapq.heappush(edges, (weight, v, neighbor))
    return mst