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.

1. Pengenalan kepada algoritma:
   Idea asas algoritma Kruskal adalah untuk mengisih semua tepi dalam graf yang disambungkan mengikut pemberatnya, dan kemudian pilih tepi dari kecil ke besar Jika tepi semasa yang dipilih tidak akan terbentuk kitaran, maka ia akan menjadi Sertai pokok rentang minimum dan tandakannya sebagai dilawati. Sehingga bilangan tepi dalam pokok rentang minimum adalah sama dengan bilangan bucu dalam graf tolak satu.
2. Langkah pelaksanaan:
   (1) Takrifkan kelas graf dan mulakan bilangan bucu dan tepi graf.
   (2) Tentukan kelas setiap tepi dan mulakan titik permulaan, titik akhir dan berat tepi.
   (3) Tulis fungsi untuk melaksanakan dan memulakan set, termasuk mencari nod akar dan menggabungkan set.
   (4) Tulis fungsi utama untuk melaksanakan algoritma Kruskal, termasuk menyusun tepi, memilih tepi satu demi satu untuk menentukan sama ada ia membentuk kitaran, menambah tepi pada pokok rentang minimum dan mengira jumlah berat pokok rentang minimum.
3. Contoh kod:

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()

4. Analisis hasil:
   Kod di atas ialah contoh biasa, membina graf tidak berwajaran yang mengandungi 6 bucu, dan menggunakan algoritma Kruskal untuk menyelesaikan pepohon rentang minimumnya. Program ini mencetak tepi dalam pokok rentang minimum dan jumlah berat pokok rentang minimum.

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!