Bagaimana untuk menulis algoritma Prim dalam Python?

Bagaimana cara menulis algoritma Prim dalam Python?

Algoritma Prim ialah algoritma klasik untuk menyelesaikan masalah pokok rentang minimum Ia boleh mencari pokok rentang minimum bagi graf bersambung tidak berarah. Artikel ini akan memperkenalkan cara menulis algoritma Prim menggunakan Python, dengan contoh kod tertentu.

Pertama, kita perlu memahami prinsip asas algoritma Prim. Algoritma bermula dari nod permulaan dan secara beransur-ansur mengembangkan sempadan pokok sehingga semua nod dalam graf diliputi. Khususnya, algoritma Prim memilih nod yang paling hampir dengan pepohon setiap kali dan menambahkannya pada pepohon spanning, dan kemudian menambah tepi yang menyambungkan nod ini ke nod dalam pepohon spanning ke set tepi calon. Kemudian, tepi dengan berat terkecil dipilih daripada set tepi calon, dan proses ini diulang sehingga pepohon spanning mengandungi semua nod.

Berikut ialah contoh kod menggunakan Python untuk melaksanakan algoritma Prim:

import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

    def printMST(self, parent):
        print("Edge     Weight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "    ", self.graph[i][parent[i]])

    def minKey(self, key, mstSet):
        min = sys.maxsize
        min_index = None

        for v in range(self.V):
            if key[v] < min and not mstSet[v]:
                min = key[v]
                min_index = v

        return min_index

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        mstSet = [False] * self.V

        parent[0] = -1

        for _ in range(self.V):
            u = self.minKey(key, mstSet)
            mstSet[u] = True

            for v in range(self.V):
                if self.graph[u][v] > 0 and not mstSet[v] and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        self.printMST(parent)

# 测试示例
g = Graph(5)
g.graph = [[0, 2, 0, 6, 0],
           [2, 0, 3, 8, 5],
           [0, 3, 0, 0, 7],
           [6, 8, 0, 0, 9],
           [0, 5, 7, 9, 0]]

g.primMST()

Dalam kod di atas, kelas Graf pertama kali ditakrifkan, yang mengandungi operasi asas graf. Dalam kaedah primMST, kaedah minKey digunakan untuk memilih nod yang sepadan dengan tepi dengan berat terkecil dalam set kelebihan calon, dan kemudian mengemas kini tatasusunan kunci dan induk.

Dalam contoh ujian, kami mencipta graf yang mengandungi 5 nod dan memberikan perwakilan matriks bersebelahan. Output kod ialah tepi pokok rentang minimum dan beratnya.

Ringkasnya, kesederhanaan dan kebolehbacaan Python menjadikannya agak mudah untuk melaksanakan algoritma Prim. Dengan memahami prinsip asas algoritma Prim dan menggunakan contoh kod di atas, anda boleh menulis dan menjalankan pelaksanaan algoritma Prim dengan mudah. Saya harap artikel ini akan membantu anda mempelajari algoritma Prim!

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma Prim dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!