ក្បួនដោះស្រាយរបស់ Kruskal
ក្បួនដោះស្រាយលោភដែលរកឃើញមែកធាងគ្របដណ្តប់តូចបំផុតសម្រាប់ក្រាហ្វទម្ងន់គ្មានទិសដៅដោយការបន្ថែមគែមតាមលំដាប់ទម្ងន់កើនឡើង។
Visualization
Details
Analogy
ស្រមៃថាអ្នកកំពុងសាងសង់ប្រព័ន្ធរថភ្លើងដើម្បីតភ្ជាប់ទីក្រុងជាច្រើន ហើយអ្នកមានបញ្ជីនៃផ្លូវរថភ្លើងដែលអាចធ្វើទៅបានទាំងអស់ និងថ្លៃដើមរបស់ពួកវា។ ក្បួនដោះស្រាយរបស់ Kruskal ដូចជាការចាប់ផ្តើមគ្មានផ្លូវរថភ្លើង។ អ្នកមើលបញ្ជីរបស់អ្នក ហើយសាងសង់ផ្លូវរថភ្លើងដែលថោកបំផុតរវាងទីក្រុងណាមួយពីរ។ បន្ទាប់មកអ្នកសាងសង់ផ្លូវរថភ្លើងថោកបន្ទាប់។ អ្នកបន្តនេះ ប៉ុន្តែអ្នករំលងផ្លូវណាមួយដែលនឹងបង្កើតរង្វង់បិទជាមួយផ្លូវដែលអ្នកបានសាងសង់រួចហើយ។ អ្នកឈប់នៅពេលទីក្រុងទាំងអស់ត្រូវបានតភ្ជាប់។
Purpose
ដើម្បីរកឃើញមែកធាងគ្របដណ្តប់តូចបំផុត (MST) ដោយការតម្រៀបគែមទាំងអស់តាមទម្ងន់ និងបន្ថែមពួកវាទៅមែកធាងប្រសិនបើពួកវាមិនបង្កើតវដ្តទេ។
Use Cases
ការរចនាបណ្តាញ ការរចនាសៀគ្វី និងការចាត់ជាក្រុម។ វាមានគំនិតសាមញ្ញ និងអាចមានប្រសិទ្ធភាពជាងក្បួនដោះស្រាយរបស់ Prim លើក្រាហ្វស្រាល។
Algorithm Steps
sort all edges by weight ascending
initialize union-find (disjoint set)
for each edge (u, v) in sorted order:
if find(u) != find(v):
add edge to MST
union(u, v)
if MST has V-1 edges: break
return MST
Explanation
What's Happening?
តម្រៀបគែមទាំងអស់តាមទម្ងន់។ គែមថោកបំផុតគឺ (A-D) និង (C-E) ទាំងពីរមានទម្ងន់ 5។
Code Implementation
def kruskal(edges, num_vertices):
parent = list(range(num_vertices))
def find(i):
if parent[i] == i:
return i
parent[i] = find(parent[i])
return parent[i]
def union(i, j):
root_i = find(i)
root_j = find(j)
if root_i != root_j:
parent[root_i] = root_j
return True
return False
mst = []
edges.sort(key=lambda item: item[2])
for u, v, weight in edges:
if union(u, v):
mst.append((u, v, weight))
return mst