Rumah > Artikel > pembangunan bahagian belakang > Bagaimana untuk melaksanakan algoritma Kruskal menggunakan Python?
Bagaimana untuk melaksanakan algoritma Kruskal menggunakan Python?
Pengenalan:
Algoritma Kruskal ialah algoritma klasik untuk menyelesaikan pepohon rentang minimum, yang boleh mencari pepohon rentang dengan jumlah berat minimum dalam graf berwajaran yang disambungkan. Artikel ini akan memperkenalkan cara melaksanakan algoritma Kruskal menggunakan Python dan memberikan contoh kod terperinci.
class Graph: def __init__(self, vertices): self.V = vertices # 顶点数 self.graph = [] # 添加边 def add_edge(self, u, v, weight): self.graph.append([u, v, weight]) # 查找根节点 def find(self, parent, i): if parent[i] == i: return i return self.find(parent, parent[i]) # 合并集合 def union(self, parent, rank, x, y): root_x = self.find(parent, x) root_y = self.find(parent, y) if rank[root_x] < rank[root_y]: parent[root_x] = root_y elif rank[root_x] > rank[root_y]: parent[root_y] = root_x else: parent[root_y] = root_x rank[root_x] += 1 # 克鲁斯卡尔算法 def kruskal_algorithm(self): result = [] i = 0 e = 0 self.graph = sorted(self.graph, key=lambda item: item[2]) # 按照权值排序 parent = [] rank = [] for node in range(self.V): parent.append(node) rank.append(0) while e < self.V - 1: u, v, weight = self.graph[i] i += 1 x = self.find(parent, u) y = self.find(parent, v) if x != y: e += 1 result.append([u, v, weight]) self.union(parent, rank, x, y) # 打印最小生成树 print("最小生成树:") for u, v, weight in result: print(f"{u} -- {v} {weight}") # 计算最小生成树的总权值 total_weight = sum(weight for u, v, weight in result) print("最小生成树的总权值:", total_weight) if __name__ == '__main__': g = Graph(6) g.add_edge(0, 1, 4) g.add_edge(0, 2, 3) g.add_edge(1, 2, 1) g.add_edge(1, 3, 2) g.add_edge(2, 3, 4) g.add_edge(2, 4, 3) g.add_edge(3, 4, 2) g.add_edge(3, 5, 1) g.add_edge(4, 5, 6) g.kruskal_algorithm()
Kesimpulan:
Algoritma Kruskal ialah kaedah yang cekap untuk menyelesaikan pepohon rentang minimum graf yang bersambung Dengan mengisih tepi dan mencantumkan set, pokok rentang dengan jumlah berat minimum boleh diperolehi. Menggunakan Python untuk melaksanakan algoritma Kruskal boleh membantu kami memahami dengan lebih baik prinsip dan proses algoritma, dan menggunakannya dengan mudah untuk masalah praktikal.
Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma Kruskal menggunakan Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!